找到gcd（a ^ n，c），其中C，a，n和c在1到10 ^ 9之间变化
我们必须找到两个数字的GCD，其中一个数字可以和（109^109）一样大，而这些数字不能存储在long或任何其他数据类型中。因此，如果数字为a=10248585，n=1000000，b=12564，则GCD（a^n，b）的结果将为9。
由于数字非常长，因此我们无法使用欧几里得算法。我们必须使用O（logn）复杂度的模幂。
示例
#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
热门推荐
10 香港老妈结婚祝福语简短
11 毕业立体贺卡祝福语简短
12 简短新年年会祝福语
13 评论小品祝福语大全简短
14 恭喜师兄结婚祝福语简短
15 员工集体辞职祝福语简短
16 高中新生祝福语 简短
17 装修祝福语男生搞笑简短
18 生日开业蛋糕祝福语简短