Đếm cặp (A ≤ N, B ≤ N) sao cho GCD(A, B) = B trong C++

Cho số N. Đếm cặp (A, B) với 1 ≤ A ≤ N, 1 ≤ B ≤ N sao cho GCD(A, B) = B.

Ví dụ

Đầu vào: N = 5
Đầu ra: 10
Giải thích: Các cặp: (1,1), (2,1), (3,1), (4,1), (5,1), (2,2), (3,3), (4,2), (4,4), (5,5).

Đầu vào: N = 50
Đầu ra: 207.

Phương pháp 1: Vét cạn (Naive)

Duyệt mọi cặp (i, j), tính GCD, kiểm tra GCD == j.

Phương pháp 2: Hiệu quả (Toán học)

GCD(A, B) = B ⟺ A là bội số của B. Với mỗi B, số bội của B trong [1, N] là ⌊N/B⌋. Tổng ∑_{B=1}^{N} ⌊N/B⌋. Tối ưu bằng cách nhóm các B có cùng giá trị ⌊N/B⌋.

Ví dụ triển khai (Hiệu quả)

#include <bits/stdc++.h>
using namespace std;

int Count_pairs(int N) {
    int count = 0;
    int temp = N;
    int i = 1;
    while (i <= N) {
        int j = N / temp;
        count += temp * (j - i + 1);
        i = j + 1;
        temp = N / i;
    }
    return count;
}

int main() {
    int N = 4;
    cout << "Count number of pairs (A <= N, B <= N) such that gcd (A , B) is B are: " << Count_pairs(N);
    return 0;
}

Kết quả

Count number of pairs (A <= N, B <= N) such that gcd (A , B) is B are: 8