資料結構
網路
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 次瀏覽
廣告