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

isdkz

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

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

下面是修复后的代码：

#include <stdio.h>

long long int powerMod(long long int a, long long int b, long long int p) {
    long long int res = 1;
    while (b > 0) {
        if (b & 1) {
            res = (res * a) % p;
        }
        a = (a * a) % p;
        b >>= 1;
    }
    return res;
}

int main() {
    long long int a, b, p;
    scanf("%lld%lld%lld", &a, &b, &p);
    long long int mod = powerMod(a, b, p);
    printf("%lld", mod);
    return 0;
}

这里定义了一个 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 次方可能需要非常长的时间，这也可能是你的代码只对了一半的原因。

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

#include<stdio.h>

long long quick_pow(long long a, long long b, long long p) {
    long long result = 1;
    while (b > 0) {
        if (b & 1) {
            result = result * a % p;
        }
        a = a * a % p;
        b >>= 1;
    }
    return result;
}

int main() {
    long long a, b, p;
    scanf("%lld%lld%lld", &a, &b, &p);
    printf("%lld", quick_pow(a, b, p));
    return 0;
}

这个代码中，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代码示例：

#include<stdio.h>long long int modular_exponentiation(long long int a, long long int b, long long int p) {    long long int result = 1;    while (b > 0) {        if (b % 2 == 1) {            result = (result * a) % p;        }        a = (a * a) % p;        b /= 2;    }    return result;}int main() {    long long int a, b, p;    scanf("%lld%lld%lld", &a, &b, &p);    long long int mod = modular_exponentiation(a, b, p);    printf("%lld", mod);    return 0;}

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

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

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