TIOJ-2095

發表於 更新於 Disqus：

求$a^{b^c}\mod 880301(1\le a,b,c\le 10^9)$(880301是質數)。
有人寫了一個快速冪函數，不過爛了，求會出現問題的測資。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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';
}

很正常的快速冪函數，中間用了三個if到處特判有夠危險。
果然問題出在這裡，當A=0, B=0(雖然數學上未定義，但這裡是模數)，mypow會回傳1而非0。
但原問題的條件不允許輸出0。然而$b^c\mod p-1$這一項可以讓她變零。
所以輸出p p-1 1就好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;
/*-----------------------------------------------------------------------------------------------------*/

signed main() {
	cout << "880301 880300 1\n";

	return 0;
}