d636: 大爆炸bomb

2019-09-02

內容

2^31 是 2 的 31 次方的意思(2147483648)
10^100 這個數字意味著 1 後面有 100 個 0
魔法師小米企鵝因為練功的時候一邊唸咒語一邊打瞌睡
居然莫名其妙召喚了好多個這種可怕的數學題目…
幫幫睡著的小米企鵝好嗎？

輸入

每個測資點僅一組測資，不必 EOF 讀檔。
測資包含一列兩個數字 a 和 b (1<=a<=65535 , 1<=b<=2147483647)

2 31

輸出

請輸出 a^b 的值，為了避免數字太大，將結果 mod10007 輸出就可以了！

1462

解題思路

用費馬小定理求解。

完整程式碼

AC (2ms, 104KB)

#include <stdio.h>
#define MOD 10007

int flt(int a, int b)
{
    int res = 1, next = a % MOD;
    for (int i = 0; i < 32; i++)
    {
        if (b & 1)
            res = res * next % MOD;
        next = next * next % MOD;
        b >>= 1;
    }
    return res;
}

int main()
{
    int a, b;
    scanf(" %d %d", &a, &b);
    printf("%d\n", flt(a, b));
    return 0;
}