找到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 婆婆高寿祝福语大全简短