数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会科学
时装研究
法律学习在 C++ 中找到 gcd(a^n, c)，其中 a、n 和 c 在 1 至 10^9 之间有所变化
我们必须找到两个数字的最大公约数，其中一个数字可能高达 (109 ^ 109)，不能存储在某些数据类型中，比如 long 或其他任何类型。因此，如果数字 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
更新于：2019 年 12 月 19 日
58 次浏览
广告