求 a 的 b 次方对 p 取模的值，其中 a,b,p≤1e18,我的代码运行只对了一半

isdkz

问题在于使用了浮点数的 pow 函数来计算 a 的 b 次方。浮点数的精度有限，当 a 或 b 较大时，可能会导致精度丢失，从而得到错误的结果。

解决这个问题的方法是使用快速幂算法来计算 a 的 b 次方。快速幂算法通过不断地将指数 b 进行二分，从而减少乘法的次数，提高计算效率。

下面是修复后的代码：

1. #include <stdio.h>
   
2. 
   
3. long long int powerMod(long long int a, long long int b, long long int p) {
   
4.     long long int res = 1;
   
5.     while (b > 0) {
   
6.         if (b & 1) {
   
7.             res = (res * a) % p;
   
8.         }
   
9.         a = (a * a) % p;
   
10.         b >>= 1;
    
11.     }
    
12.     return res;
    
13. }
    
14. 
    
15. int main() {
    
16.     long long int a, b, p;
    
17.     scanf("%lld%lld%lld", &a, &b, &p);
    
18.     long long int mod = powerMod(a, b, p);
    
19.     printf("%lld", mod);
    
20.     return 0;
    
21. }
    

复制代码

这里定义了一个 powerMod 函数，用于计算 a 的 b 次方对 p 取模的值。在该函数中，使用了循环和位运算来实现快速幂算法。每次循环中，如果当前的指数 b 是奇数，就将结果 res 乘以 a，并对 p 取模；然后将 a 自乘，并对 p 取模；最后将指数 b 右移一位，相当于将其除以 2。

这样，通过不断地将指数 b 进行二分，就可以在 O(log b) 的时间复杂度内计算出 a 的 b 次方对 p 取模的值，即所求的结果。

陶远航

你的代码中有一个主要问题，那就是当 a 和 b 的值非常大时，pow(a, b) 的结果可能会超出 double 类型的表示范围，导致结果不准确。此外，当 a 和 b 的值非常大时，计算 a 的 b 次方可能需要非常长的时间，这也可能是你的代码只对了一半的原因。

为了解决这个问题，你可以使用快速幂算法，并结合取模运算的性质。下面是一个使用快速幂算法的示例代码：

1. #include<stdio.h>
   
2. 
   
3. long long quick_pow(long long a, long long b, long long p) {
   
4.     long long result = 1;
   
5.     while (b > 0) {
   
6.         if (b & 1) {
   
7.             result = result * a % p;
   
8.         }
   
9.         a = a * a % p;
   
10.         b >>= 1;
    
11.     }
    
12.     return result;
    
13. }
    
14. 
    
15. int main() {
    
16.     long long a, b, p;
    
17.     scanf("%lld%lld%lld", &a, &b, &p);
    
18.     printf("%lld", quick_pow(a, b, p));
    
19.     return 0;
    
20. }
    

复制代码

这个代码中，quick_pow 函数使用了快速幂算法来计算 a 的 b 次方对 p 取模的值。这个算法的时间复杂度是 O(log b)，所以即使 a 和 b 的值非常大，也可以在合理的时间内得到结果。同时，由于在每一步都进行了取模运算，所以不会出现结果超出 long long int 类型表示范围的问题。
请注意，本回答来自GPT-4
如果问题已经解决，请设置最佳答案

Mike_python小

思路解析:

在给定a、b和p的情况下，计算a的b次方对p取模的值可以使用快速幂算法。这个算法可以在O(log b)的时间复杂度下完成计算。

具体步骤如下：

1. 初始化一个变量result为1，用于保存最终的结果。
2. 通过循环迭代计算，每次迭代将b除以2并向下取整，同时将a的平方对p取模。
3. 如果当前b的最低位为1，则将result乘以当前迭代的a的值，并对p取模。
4. 最后返回result的值即为a的b次方对p取模的结果。

下面是修改后的C代码示例：

2. #include<stdio.h>
4. long long int modular_exponentiation(long long int a, long long int b, long long int p) {
5.     long long int result = 1;
6.     while (b > 0) {
7.         if (b % 2 == 1) {
8.             result = (result * a) % p;
9.         }
10.         a = (a * a) % p;
11.         b /= 2;
12.     }
13.     return result;
14. }
16. int main() {
17.     long long int a, b, p;
18.     scanf("%lld%lld%lld", &a, &b, &p);
19.     long long int mod = modular_exponentiation(a, b, p);
20.     printf("%lld", mod);
21.     return 0;
22. }

复制代码

这段代码将使用快速幂算法来计算a的b次方对p取模的结果。通过将指数b按位进行分解和计算，可以极大地减少计算时间。

希望这个回答对你有帮助！如果你有任何其他问题，请随时提问。

球一个最佳答案谢谢啦！这对我非常重要！