আমাদের দুটি সংখ্যার GCD খুঁজে বের করতে হবে যার মধ্যে একটি সংখ্যা (109^ 109) এর মতো বড় হতে পারে, যেটি দীর্ঘ বা অন্য কোনো ডেটা টাইপের মধ্যে সংরক্ষণ করা যায় না। তাই যদি সংখ্যাগুলো হয় a =10248585, n =1000000, b =12564, তাহলে GCD(a^n, b) এর ফলাফল হবে 9।
যেহেতু সংখ্যাগুলি খুব দীর্ঘ, আমরা ইউক্লিডীয় অ্যালগরিদম ব্যবহার করতে পারি না। আমাদের O(log n) জটিলতার সাথে মডুলার সূচক ব্যবহার করতে হবে।
উদাহরণ
#include<iostream> #include<algorithm> using namespace std; long long power(long long a, long long n, long long b) { long long res = 1; a = a % b; while (n > 0) { if (n & 1) res = (res*a) % b; n = n>>1; a = (a*a) % b; } return res; } long long bigGCD(long long a, long long n, long long b) { if (a % b == 0) return b; long long exp_mod = power(a, n, b); return __gcd(exp_mod, b); } int main() { long long a = 10248585, n = 1000000, b = 12564; cout << "GCD value is: " << bigGCD(a, n,b); }
আউটপুট
GCD value is: 9