ZeroJudge 解題筆記：d636. 大爆炸bomb

作者：王一哲
日期：2025年9月8日


ZeroJudge 題目連結：d636. 大爆炸bomb

解題想法

這題考快速冪、平方求冪 (exponentiating by squaring)。

Python 程式碼

使用時間約為 19 ms，記憶體約為 3.3 MB，通過測試。

def exp(x, y, p):  # x 的 y 次方，取除以 p 的餘數
    t = 1  # 儲存結果用的變數
    while y:  # 如果 y 不等於 0 繼續執行
        if y&1: t = t*x%p  # 若 y 與 1 取 and 為 1，更新 t，乘上 x 再取 mod p
        y >>= 1  # y 除以 2
        x = x*x%p  # 更新 x，乘上 x 再取 mod p
    return t  # 回傳 t

print(exp(*map(int, input().split()), 10007))  # 印出 exp(a, b, p)

用 pow 作弊，使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

print(pow(*map(int, input().split()), 10007))

C++ 程式碼

使用時間約為 2 ms，記憶體約為 76 kB，通過測試。

#include <cstdio>
typedef long long LL;
using namespace std;

LL exp(LL x, LL y, LL p) {
    LL t = 1;
    while(y) {
        if (y&1) t = t*x%p;
        y >>= 1;
        x = x*x%p;
    }
    return t;
}

int main() {
    LL a, b, p = 10007;
    scanf("%lld %lld", &a, &b);
    printf("%lld\n", exp(a, b, p));
    return 0;
}