用C++实现 给出正整数x和n个正整数ai,求x的ai次方 mod p。输入格式:第一行,两个正整数下,你,。第二行,n个正整数ai
时间: 2024-05-08 15:18:40 浏览: 115
以空格分隔。第三行,一个正整数p。输出格式:一个整数,即x的ai次方 mod p的值。
好的,我明白了您的问题。这个问题可以通过快速幂算法来解决。我可以为您提供一个 C 语言实现的代码示例:
```
#include <stdio.h>
// 快速幂算法
int pow_mod(int x, int a, int p) {
int ans = 1 % p;
x %= p;
while (a) {
if (a & 1) ans = (long long)ans * x % p;
x = (long long)x * x % p;
a >>= 1;
}
return ans;
}
int main() {
int x, n, a[1005], p;
scanf("%d%d", &x, &n);
for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
scanf("%d", &p);
int ans = 1;
for (int i = 0; i < n; ++i)
ans = (long long)ans * pow_mod(x, a[i], p) % p; // 依次求 x^ai mod p 并求积
printf("%d\n", ans);
return 0;
}
```
您可以将您的输入复制到上面的代码中进行测试,看看是否可以得到正确的答案。请注意,这个代码适用于 x, a[i], p 都在 int 范围内的情况,如果您的输入数据超出了 int 的范围,需要对代码进行修改。
阅读全文