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

看Integer Overflow为什么是负数，为什么总是-8，好吧，比我聪明的人会回答那个。

Answer 2

int 最多可以保存 2^31 - 1 的值，所以你基本上有一个溢出（实际上它导致 Undefined Behaviour 与溢出 unsigned 形成对比类型）。

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

我们可以使用以下属性: (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 - 这足以满足您的限制并防止不必要和不需要的转换在有符号和无符号之间。

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

Power function in C gives the same output for large numbers

c

exponentiation