用c++帮我写一个扩展的欧几里得算法的函数(两个参数)
时间: 2023-11-22 19:55:40 浏览: 25
好的,以下是一个使用扩展欧几里得算法求解两个数的最大公约数及其系数的C++函数:
```cpp
#include <iostream>
using namespace std;
int extgcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
int d = extgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
int main() {
int a = 24, b = 18, x, y;
int d = extgcd(a, b, x, y);
cout << "gcd(" << a << ", " << b << ") = " << d << endl;
cout << "x = " << x << ", y = " << y << endl;
return 0;
}
```
该函数的参数为两个整数 `a` 和 `b`,返回结果为它们的最大公约数 `d`,同时通过引用参数 `x` 和 `y` 返回满足 `ax + by = d` 的一组整数解。
函数的实现中使用了递归调用,在每一次递归中交换了 `x` 和 `y` 的值,并根据扩展欧几里得算法的原理计算出新的 `x` 和 `y` 的值。最终返回的 `d` 即为两个数的最大公约数。
相关问题
用c++和AKS 算法写一个判断素数的函数
好的,以下是用 C++ 实现 AKS 算法判断素数的函数:
```cpp
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {
if (b == 0) return a;
return gcd(b, a % b);
}
ll power(ll a, ll b, ll mod) {
ll res = 1;
while (b) {
if (b & 1) res = (__int128) res * a % mod;
a = (__int128) a * a % mod;
b >>= 1;
}
return res;
}
bool is_prime(ll n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
ll r = sqrt(n);
for (ll i = 5; i <= r; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) return false;
}
if (n <= r * r) return true;
ll d = n - 1;
while (d % 2 == 0) d /= 2;
vector<ll> a = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
for (ll i = 0; i < a.size(); i++) {
if (a[i] >= n) break;
ll x = power(a[i], d, n);
if (x == 1 || x == n - 1) continue;
bool flag = false;
while (d != n - 1) {
x = (__int128) x * x % n;
d *= 2;
if (x == 1) return false;
if (x == n - 1) {
flag = true;
break;
}
}
if (!flag) return false;
}
return true;
}
bool is_prime_ak(ll n) {
if (n <= 1) return false;
if (n == 2 || n == 3 || n == 5) return true;
if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0) return false;
ll r = 2;
while (r * r <= n) {
if (n % r == 0) {
if (gcd(r, n / r) != 1) return false;
else return true;
}
r++;
}
ll m = ((ll)log2(n) << 1) + 1;
for (ll r = 2; r <= m; r++) {
if (power(r, n, n) != r) return false;
}
return true;
}
int main() {
ll n;
cin >> n;
if (is_prime(n)) {
cout << "AKS says: " << is_prime_ak(n) << endl;
cout << "It is a prime number!" << endl;
} else {
cout << "AKS says: " << is_prime_ak(n) << endl;
cout << "It is not a prime number!" << endl;
}
return 0;
}
```
其中,`is_prime` 函数采用了 Miller-Rabin 算法进行素数判断,而 `is_prime_ak` 函数则是 AKS 算法的实现。
需要注意的是,在 AKS 算法中,判断 $a$ 和 $n$ 是否互质时,可以使用欧几里得算法来求最大公因数,因为 AKS 算法的时间复杂度已经足够低,不需要使用更快的算法。此外,在 AKS 算法中,我们需要使用 128 位整数来进行快速幂运算,以避免数据溢出。
欧几里得算法输入两个正整数,求其最大公约数。c++
欧几里得算法可以用以下 C 代码实现:
int gcd(int a, int b) {
if (b == ) {
return a;
} else {
return gcd(b, a % b);
}
}
其中,a 和 b 分别为输入的两个正整数,函数返回它们的最大公约数。