นับคู่ (A ≤ N, B ≤ N) ที่ gcd(A, B) = B ใน C++

เราได้รับจำนวนเต็ม N เป้าหมายคือนับคู่ (A, B) ที่ 1 ≤ A ≤ N, 1 ≤ B ≤ N และ gcd(A, B) = B

ตัวอย่าง

อินพุต: N = 5

เอาต์พุต: 10

คำอธิบาย: คู่ที่เป็นไปได้: (1,1), (2,1), (3,1), (4,1), (5,1), (2,2), (3,3), (4,2), (4,4), (5,5)

อินพุต: N = 50

เอาต์พุต: 207

แนวทางการแก้ปัญหา

วิธีแบบง่าย (Naive O(N²))

วนลูปทุกคู่ (i, j) คำนวณ gcd(i, j) ถ้าเท่ากับ j ให้นับ

วิธีที่มีประสิทธิภาพ (O(√N))

gcd(A, B) = B ⟺ B หาร A ลงตัว (A เป็น multiple ของ B)
สำหรับแต่ละ B (1 ถึง N) จำนวน A ที่เป็น multiple ของ B และ ≤ N คือ ⌊N/B⌋
คำตอบ = Σ_{B=1}^{N} ⌊N/B⌋
สามารถคำนวณได้ใน O(√N) โดยจัดกลุ่มค่า ⌊N/B⌋ ที่เท่ากัน

การนำไปใช้ (Implementation)

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

// Naive approach
int GCD(int A, int B) {
    if (A == 0) return B;
    if (B == 0) return A;
    if (A == B) return A;
    if (A > B) return GCD(A - B, B);
    return GCD(A, B - A);
}

int count_pairs_naive(int N) {
    int count = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (GCD(i, j) == j) count++;
        }
    }
    return count;
}

// Efficient approach O(√N)
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;
}

เอาต์พุต

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