TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

75.0% (6/8)

Submission's AC Ratio

46.2% (6/13)

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

Sample Input

Sample Output

Hints

Problem Source

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144