TopCoder

FHVirus
$\Huge 8e7 二分圖判斷範例程式碼有錯,道歉!$

User's AC Ratio

66.7% (22/33)

Submission's AC Ratio

48.1% (37/77)

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

Sample Input

Sample Output

Hints

Problem Source

Subtasks

No. Testdata Range Score

Testdata and Limits

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