C++ এ অজানা পণ্যের প্রদত্ত পণ্য থেকে সর্বাধিক GCD

ধরুন আমরা দুটি পূর্ণসংখ্যা N এবং P। P হল N অজানা পূর্ণসংখ্যার গুণফল। আমাদের সেই পূর্ণসংখ্যাগুলির 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 হল a₁ এর GCD , a₂ , … a_n . তারপর ai হল g এর একাধিক, এবং P হল (a₁ * a₂ * … * a_n ) অবশ্যই g ⁿ এর গুণিতক হতে হবে . উত্তর হল সর্বাধিক g যেমন g ⁿ mod P =0। এখন ধরুন P =k1 ^p1 * k2 ^p1 * … * kn ^pn . g এর মত হতে হবে, তারপর g কে বড় করতে হলে p_i বেছে নিতে হবে =p_i / 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