1719 測資加強 已 rejudge
2095 . 快速冪（駭客題）
TopCoder
Tags
Description
Original Description
給三個正整數 $a,b,c$ ，求 $a^ {b^ c} \bmod 880301$ 。 （880301是一個質數）
Original Input Format
輸入的第一行包含三個用空白分隔的正整數 $a,b,c$ 。
- $1 \le a,b,c \le 1000000000$
Original Output Format
請輸出一個數字，代表 $a^ {b^ c} \bmod 880301$ 的值。
Original Sample Input
2 2 2
Original Sample Output
16
Original Limits
- Time Limit: 1 second
- Memory Limit: 256 MB
Program To Be Hacked
#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'; }
Judge Method
學過快速冪的學姐一看就知道這題只要做兩次快速冪就好了，於是她寫出了一個快速冪函數
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)$ 就好了。
但這份程式碼卻是有問題的，請找出一個讓這份程式碼得出錯誤答案的測試資料!
Sample Code
以下程式碼能產生本題合法但一定不會讓你得到 AC 的測試資料。
#include <cstdio> int main() { printf("1 1 1\n"); }
Input Format
Output Format
Hints
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|