Đếm cặp số tự nhiên có GCD bằng số cho trước trong C++

Cho start, end, number. Tìm số cặp (A,B) trong khoảng [start, end] có GCD(A,B) = number.

Ví dụ

Đầu vào − start=5, end=20, number=8

Đầu ra − 3

Giải thích − (8,8), (8,16), (16,8).

Đầu vào − start=5, end=20, number=7

Đầu ra − 2

Giải thích − (21,28), (28,21) (trong khoảng 20-30 theo ví dụ gốc).

Phương pháp giải

Cách 1 (naive): 2 vòng lặp i,j = start..end, kiểm tra GCD(i,j)==number.

Cách 2 (hiệu quả): Để GCD(i,j)=number, cả i,j phải chia hết cho number. Biến đổi: start' = ceil(start/number), end' = floor(end/number). Đếm cặp (i,j) trong [start', end'] có GCD(i,j)=1.

• Hàm GCD(a,b) đệ quy Euclid.
• Cách 1: lặp start..end 2 lần.
• Cách 2: cập nhật start = (start+number-1)/number, end = end/number, lặp đếm GCD==1.

Ví dụ code (naive)

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

int GCD(int a, int b) { return b ? GCD(b, a % b) : a; }

int GCD_pairs(int start, int end, int number) {
    int count = 0;
    for (int i = start; i <= end; i++)
        for (int j = start; j <= end; j++)
            if (GCD(i, j) == number) count++;
    return count;
}

int main() {
    int start = 10, end = 30, number = 10;
    cout << "Count of pairs of natural numbers with GCD equal to given number are: " << GCD_pairs(start, end, number) << endl;
    return 0;
}

Đầu ra

Count of pairs of natural numbers with GCD equal to given number are: 7

Ví dụ code (hiệu quả)

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

int GCD(int a, int b) { return b ? GCD(b, a % b) : a; }

int GCD_pairs(int start, int end, int number) {
    int count = 0;
    for (int i = start; i <= end; i++)
        for (int j = start; j <= end; j++)
            if (GCD(i, j) == 1) count++;
    return count;
}

int main() {
    int start = 10, end = 30, number = 10;
    start = (start + number - 1) / number;
    end = end / number;
    cout << "Count of pairs of natural numbers with GCD equal to given number are: " << GCD_pairs(start, end, number) << endl;
    return 0;
}

Đầu ra

Count of pairs of natural numbers with GCD equal to given number are: 7