Imgur
目前猜測,可能需要做快速冪。有一測資點 TLE 。

*7/22 更新:的確使用快速冪可以解決 TLE 的問題。

d636: 大爆炸bomb:

內容:

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

輸入說明:

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

輸出說明 :

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

範例輸入:

2 31

範例輸出:

1462

提示 :
1.名題百選
2.共三個測資點30%、35%、35%,
第一個測資點即範例測資。
標籤:
數論 餘數

65分 解:
#include <iostream>
using namespace std;
int main(){	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int a,b;
	int tmp = 1;	
	cin >> a >> b;
	while(b--){
		tmp = tmp * a;
		tmp = tmp % 10007;
	}
	cout << tmp;
}
100分 解,使用快速冪(倍增):

線上 IDE

#include <iostream>
using namespace std;
int PowerMod(int a, int b, int c);  
int main(){  
	cin.tie(0);
	ios_base::sync_with_stdio(false);
    int a,b;
    cin >> a >> b;
    cout << PowerMod(a,b,10007);
}
 
int PowerMod(int a,int b,int c){  
    int ans = 1;
    a = a % c;
    while(b>0){
        if(b%2==1)
            ans = (ans * a) % c;
        b = b / 2;
        a = (a * a) % c;
    }
    return ans;
}

引用社團學長不詳盡證明:

假設
m=ap+q
n=bp+k
你發現他們個別對p取餘數一個是q一個是k
那你把他們相乘會得到apbp+bpq+apk+qk
然後你發現把他們個別取餘數之後的相乘再取餘
數的答案和相乘後取餘數的答案一樣
就這樣 所以你邊乘邊模不會錯

ZJ

pixiv

快速冪 @ 百度文库

快速冪 @ 百度文库 pdf