給三個正整數 $a,b,c$ ,求 $a^ {b^ c} \bmod 880301$ 。 (880301是一個質數)
輸入的第一行包含三個用空白分隔的正整數 $a,b,c$ 。
請輸出一個數字,代表 $a^ {b^ c} \bmod 880301$ 的值。
2 2 2
16
#include<iostream>
using namespace std;
long long mypow(long long A,long long B,long long M){ //calculate A^B % M
A%=M;
if(M==1) return 0;
if(B==0) return 1;
if(A==0) return 0;
long long mid=mypow(A,B/2,M);
if(B%2) return mid*mid%M*A%M;
else return mid*mid%M;
}
int main(){
long long a,b,c,p=880301;
cin>>a>>b>>c;
cout<<mypow(a,mypow(b,c,p-1),p)<<'\n';
}
學過快速冪的學姐一看就知道這題只要做兩次快速冪就好了,於是她寫出了一個快速冪函數
long long mypow(long long A,long long B,long long M){ //calculate A^B % M
A%=M;
if(M==1) return 0;
if(B==0) return 1;
if(A==0) return 0;
long long mid=mypow(A,B/2,M);
if(B%2) return mid*mid%M*A%M;
else return mid*mid%M;
}
另外由費馬小定理,我們知道
$a^ {b^ c} \equiv a^ {b^ c \bmod (p-1)} \pmod p$
所以我們只需計算 $\text{mypow} (a, \text{mypow} (b,c,p-1),p)$ 就好了。
但這份程式碼卻是有問題的,請找出一個讓這份程式碼得出錯誤答案的測試資料!
以下程式碼能產生本題合法但一定不會讓你得到 AC 的測試資料。
#include <cstdio>
int main() {
printf("1 1 1\n");
}
No. | Testdata Range | Score |
---|
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1000 | 65536 | 262144 |