如何计算a的b次方除以十的九次方加七的余数

Question

我写了一段代码计算a的b次方然后计算

pow(a,b) % 1000000007

1000000007 = pow(10,9) + 7

a

和

b

是范围内的整数

1 <= a,b <= 10000000

显然，pow(a,b) 是一个非常大的数字，所以我认为我的代码中发生了溢出。我该如何优化和修复我的代码？

    #include <stdio.h>
    #include <math.h>
    unsigned long long int power(unsigned long long int a, unsigned long long int b)
    {
            if (power(a,b) < 1000000007)
            {
                if (b == 1)
                    return a;
                else
                    return a * power(a, b-1);
            }
            else if (power(a,b) == 1000000007)
                return 0;
            else 
                return a * power(a, b-1) % 1000000007;
    }
    int main()
    {
            unsigned long long int a, b;
            scanf("%llu %llu", &a, &b);
            printf("%llu", power(a,b));
            return 0;
    }

Answer 1

这里有一个有效的求幂解：

#include <stdio.h>

unsigned long long power(unsigned long long base, unsigned long long exp, unsigned modulo)
{
    unsigned long long result = 1;
    base %= modulo;
    for (;;)
    {
        if (exp & 1)
            result = (result * base) % modulo;
        exp >>= 1;
        if (!exp)
            break;
        base = (base * base) % modulo;
    }

    return result;
}

int main(void) {
    unsigned long long int a, b;
    if(scanf("%llu %llu", &a, &b) != 2)
        return 1;
    printf("%llu\n", power(a, b, 1000000007));
    return 0;
}