GCD tối đa từ Sản phẩm chưa biết đã cho trong C ++

Giả sử chúng ta có hai số nguyên N và P. P là tích của N số nguyên chưa biết. Chúng ta phải tìm GCD của những số nguyên đó. Có thể có nhiều nhóm số nguyên khác nhau, điều đó sẽ cho cùng một kết quả. Ở đây chúng tôi sẽ sản xuất GCD, là mức tối đa trong số tất cả các nhóm có thể. Giả sử N =3 và P =24, thì các nhóm khác nhau sẽ giống như {1, 1, 24}, {1, 2, 12}, {1, 3, 8}, {1, 4, 6}, {2 , 2, 6}, {2, 3, 4}. GCD là:1, 1, 1, 1, 2, 1. Vậy câu trả lời là 2 ở đây.

Kỹ thuật mà chúng tôi thích, giả sử g là GCD của ₁ , một ₂ ,… A _n . Khi đó ai là bội số của g, và P là (a ₁ * a ₂ *… * A _n ) phải là bội số của g ⁿ . Câu trả lời là tối đa g sao cho g ⁿ mod P =0. Bây giờ giả sử P =k1 ^p1 * k2 ^p1 *… * Kn ^pn . g phải có dạng như thế này, sau đó để tối đa hóa g, chúng ta phải chọn p _i =p _i / N.

Ví dụ

#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);
}

Đầu ra

MAX GCD: 2