นับคู่ที่เป็นร่วมเฉพาะ (Coprime) จาก 1 ถึง N ใน C++

ภาพรวมปัญหา

ได้รับ Q คำถาม แต่ละคำถามมี N หาจำนวนคู่ที่ไม่มีลำดับ (unordered pairs) ที่เป็นร่วมเฉพาะ (Coprime) ในช่วง 1 ถึง N

ตัวอย่าง

Input: Q = 2, queries = [5, 6]
Output: 10, 18
Pairs for N=5: (1,1),(1,2),(1,3),(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)

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

• ใช้ Euler's Totient Function φ(n) = จำนวนเลข ≤ n ที่ร่วมเฉพาะกับ n
• จำนวนคู่ร่วมเฉพาะ ≤ N = Σ φ(i) สำหรับ i=1 ถึง N
• คำนวณ φ(i) ทั้งหมดด้วย Modified Sieve แล้วคำนวณ Prefix Sum

ตัวอย่างโค้ด C++

#include <iostream>
using namespace std;

#define N 10001
int phi[N];
int CoPrimePairs[N];

void computePhi() {
    for (int i = 1; i < N; i++) phi[i] = i;
    for (int p = 2; p < N; p++) {
        if (phi[p] == p) {
            phi[p] = p - 1;
            for (int i = 2*p; i < N; i += p)
                phi[i] = (phi[i] / p) * (p - 1);
        }
    }
}

void findCoPrimes() {
    computePhi();
    for (int i = 1; i < N; i++)
        CoPrimePairs[i] = CoPrimePairs[i-1] + phi[i];
}

int main() {
    findCoPrimes();
    int Q = 3;
    int query[] = {5, 7, 9};
    for (int i = 0; i < Q; i++)
        cout << "Query " << i+1 << ": " << CoPrimePairs[query[i]] << endl;
    return 0;
}

ผลลัพธ์

For Query 1: Number of prime pairs is 10
For Query 2: Number of prime pairs is 18
For Query 3: Number of prime pairs is 28