找到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（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
-
本文向大家介绍在C ++中找到（1 ^ n + 2 ^ n + 3 ^ n + 4 ^ n）mod 5，包括了在C ++中找到（1 ^ n + 2 ^ n + 3 ^ n + 4 ^ n）mod 5的使用技巧和注意事项，需要的朋友参考一下 在本教程中，我们将解决以下问题。 给定一个整数n，我们必须找到（1 n +2 n +3 n +4 n）％5 如果n大，则数字（1 n +2 n +3 n +4
-
本文向大家介绍计算三元组(a，b，c)的数量，以使C ++中a ^ 2 + b ^ 2 = c ^ 2和1 <= a <= b <= c <= n，包括了计算三元组(a，b，c)的数量，以使C ++中a ^ 2 + b ^ 2 = c ^ 2和1 <= a <= b <= c <= n的使用技巧和注意事项，需要的朋友参考一下 我们得到一个整数n。目标是找到满足条件的三元组（3个数字一组）- a 2
-
本文向大家介绍在C ++中找到2 ^（2 ^ A）％B，包括了在C ++中找到2 ^（2 ^ A）％B的使用技巧和注意事项，需要的朋友参考一下 在本教程中，我们将编写一个程序来计算等式2 ^（2 ^ A）％B。 我们将使用递归函数找到方程的值。让我们看看解决问题的步骤。 编写一个带有2个参数A和B的递归函数。 如果A为1，则将4％B返回为2 ^（2 ^ 1）％B = 4％B. 否则用A-1和b递归
-
本文向大家介绍在数组中找到四个元素a，b，c和d，以便在C ++中a + b = c + d，包括了在数组中找到四个元素a，b，c和d，以便在C ++中a + b = c + d的使用技巧和注意事项，需要的朋友参考一下 假设我们有一个整数列表。我们的任务是找到四个不同的整数，分别为(a,b)和(c,d)两对，这样a + b = c + d。如果有多个答案，则仅打印一个。假设数组元素像：A = [7
-
本文向大家介绍在C ++中找到一个数字X，其数字之和等于N，包括了在C ++中找到一个数字X，其数字之和等于N的使用技巧和注意事项，需要的朋友参考一下 在本教程中，我们将找到一个数字，其中一些（包括其数字）等于给定的数字N。 这个想法很简单，我们将检查给定数字的左右100个数字。N≤1000000000且总和不超过100不会被限制。 让我们看看解决问题的步骤。 初始化号码。 编写一个循环100次的
-
本文向大家介绍查找（a ^ b）％m，其中“ a”在C ++中非常大，包括了查找（a ^ b）％m，其中“ a”在C ++中非常大的使用技巧和注意事项，需要的朋友参考一下 在本教程中，我们将求解方程（a b）％m，其中a是一个非常大的数字。 公式（a b）％m =（a％m）*（a％m）... b_times。我们可以通过找到a％m的值然后将其乘以b来解决该问题。 让我们看看解决问题的步骤。 初始化