ในปัญหานี้ เราได้รับ Q Queries แต่ละอันมีตัวเลข N ภารกิจของเราในการสร้างโปรแกรมเพื่อแก้ปัญหา Queries เพื่อนับจำนวนของ coprime คู่ที่ไม่เรียงลำดับจาก 1 ถึง N ใน C++
โคไพรม์ เรียกอีกอย่างว่าจำนวนเฉพาะที่เป็นจำนวนเฉพาะหรือจำนวนเฉพาะร่วมกันคือคู่ของตัวเลขที่มีตัวประกอบเพียงตัวเดียวคือ 1.
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล :Q =2, การสืบค้น =[5, 6]
ผลผลิต :10
คำอธิบาย
คู่คือ:(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5),(3, 4 ), (3, 5), (4, 5)
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาที่มีแนวโน้มดีที่สุดคือการใช้ TotientFunction phi(N) ของออยเลอร์ phi(N) คำนวณจำนวนรวมของ co-primes จนกระทั่งค่าที่กำหนด N ฟังก์ชัน totient ของออยเลอร์คือ
$$𝛷(𝑁) =𝑁 ∏𝑁/𝑁 (1 −),$$
โดยที่ p คือตัวประกอบเฉพาะของ N.
ตอนนี้ เราจะคำนวณค่าของการนับจำนวนคู่ coprime ที่ไม่เรียงลำดับจนถึง N แล้วหาค่าของแต่ละการสืบค้นจากอาร์เรย์ที่คำนวณไว้ล่วงหน้า
ตัวอย่าง
#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<<"For Query "<<(i+1)<<": Number of prime pairs is "<<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
