C++ এ প্রদত্ত পণ্যের সাথে N পূর্ণসংখ্যার সর্বাধিক GCD

ধরুন আমরা দুটি পূর্ণসংখ্যা N এবং P। P হল N অজানা পূর্ণসংখ্যার গুণফল। আমাদের সেই পূর্ণসংখ্যাগুলির সর্বাধিক সম্ভাব্য 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।

আমরা P এর সমস্ত মৌলিক গুণনীয়ক খুঁজে বের করব এবং সেগুলিকে হ্যাশম্যাপে সংরক্ষণ করব। N পূর্ণসংখ্যার সর্বাধিক GCD থাকবে যখন মৌলিক গুণনীয়কটি সমস্ত পূর্ণসংখ্যাতে সাধারণ হবে। তাই যদি P =p₁ ^k1 * p₂ ^k2 * … * p_n ^kn . এখানে পাই হল প্রাইম ফ্যাক্টর। তাহলে সর্বাধিক GCD হবে res =p₁ ^k1/N * p₂ ^k2/N * … * p_n ^kn/N .

উদাহরণ

#include <iostream>
#include <cmath>
#include <unordered_map>
using namespace std;
long getMaxGCD(long N, long p) {
   int gcd = 1;
   unordered_map<int, int> prime_factors;
   for (int i = 2; i * i <= p; i++) {
      while (p % i == 0) {
         prime_factors[i]++;
         p /= i;
      }
   }
   if (p != 1)
      prime_factors[p]++;
   for (auto v : prime_factors)
      gcd = gcd * pow(v.first, v.second / N);
   return gcd;
}
int main() {
   long n = 3;
   long p = 24;
   cout << "MAX GCD: " << getMaxGCD(n, p);
}

আউটপুট

MAX GCD: 2