สมมติว่าเราสองจำนวนเต็ม N และ P P คือผลคูณของจำนวนเต็มไม่ทราบจำนวน เราต้องหา GCD ของจำนวนเต็มเหล่านั้น อาจมีกลุ่มของจำนวนเต็มต่างกันได้ ซึ่งจะให้ผลลัพธ์เหมือนกัน ที่นี่เราจะสร้าง GCD ซึ่งสูงที่สุดในบรรดากลุ่มที่เป็นไปได้ทั้งหมด สมมุติว่า N =3 และ P =24 จากนั้นกลุ่มต่างๆ จะเป็นเช่น {1, 1, 24}, {1, 2, 12}, {1, 3, 8}, {1, 4, 6}, {2 , 2, 6}, {2, 3, 4}. GCD คือ:1, 1, 1, 1, 2, 1 คำตอบคือ 2 ที่นี่
เทคนิคที่เราชอบ สมมติว่า g คือ GCD ของ a1 , a2 , … an . ai คือผลคูณของ g และ P คือ (a1 * a2 * … * an ) ต้องเป็นทวีคูณของ g n . คำตอบคือ max g เท่ากับว่า g n mod P =0 ทีนี้สมมติ P =k1 p1 * k2 p1 * … * kn pn . g จะต้องอยู่ในรูปแบบนี้ ดังนั้นหากต้องการขยาย g ให้ใหญ่สุด เราต้องเลือก pi =pผม / N.
ตัวอย่าง
#include <iostream>
#include <cmath>
using namespace std;
long getMaxGCD(long n, long p) {
int count = 0;
long gcd = 1;
while (p % 2 == 0) {
p >>= 1;
count++; //number of times P divided by 2
}
if (count > 0) //if p has some 2s, then
gcd = gcd* (long)pow(2, count / n);
for (long i = 3; i <= sqrt(p); i += 2) { //check for all numbers after 2
count = 0;
while (p % i == 0) {
count++;
p = p / i;
}
if (count > 0) {
gcd = gcd* (long)pow(i, count / n);
}
}
// If n in the end is a prime number
if (p > 2)
gcd = gcd* (long)pow(p, 1 / n);
return gcd;
}
int main() {
long n = 3;
long p = 24;
cout << "MAX GCD: " << getMaxGCD(n, p);
} ผลลัพธ์
MAX GCD: 2
