c - C 中的幂函数为大数提供相同的输出

Question

problem statement要求我找出 a^b 的最后一位数字。约束是 0 <= a <= 20 和 0 <= b <= 2,147,483,000。

我的代码适用于 12^8 或 6^9 或类似的数字。但是当我移动到大数区域时，比如 14^1234 或 17^148713，我总是得到 -8 的输出。

#include <stdio.h>
#include <math.h> 
int main() {
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int a;
        long long int b;
        double x, y, res;
        scanf("%d %lld", &a, &b);
        x=(double)a;
        y=(double)b;
        res = pow(x, y);
        int rem;
        rem = (int)res%10;
        printf("%d\n", rem);
    }
    return 0; }

如此奇怪的输出可能是什么原因？

除了将大数字存储在数组中(我猜是 How to calculate 2 to the power 10000000 之类的东西)之外，还有其他办法吗？

Answer 1

int 可以保存最大为 2^31 - 1 的值，因此基本上会发生溢出(实际上它会导致 Undefined Behaviour 与溢出无符号类型形成对比) .

正如@PaulR 在对您的问题的评论中所指出的，一般的想法是滥用模幂运算的某些属性。简而言之:您需要使数字“足够小”以防止溢出并能够获得所需的结果。

我们可以使用以下属性:(a * b) % m == (a % m) * (b % m)。在代码中它可能看起来像这样:

const unsigned int m = 10;  // our modulus
while(t--)
{
    ...                     // read 'a' and 'b'

    unsigned int res = 1;   // last digit of a^b (e.g. res == (a^b % m))
    for (unsigned int i = 0; i < b; ++i)
    {
        res *= a;           // rising to power i
        res %= m;           // keep res small !
    }

    ...                     // you get desired result
}

注意:将 a 和 b 声明为 unsigned int - 这足以满足您的限制，并且防止有符号和无符号之间不必要和不需要的转换。