Description
你被要求设计一个计算器完成以下三项任务：
1、给定y、z、p，计算y^z mod p 的值；
2、给定y、z、p，计算满足xy ≡z(mod p)的最小非负整数x；
3、给定y、z、p，计算满足y^x ≡z(mod p)的最小非负整数x。
为了拿到奖品，全力以赴吧！
Input
输入文件calc.in 包含多组数据。
第一行包含两个正整数T、L，分别表示数据组数和询问类型（对于一个测试点内的所有数
据，询问类型相同）。
以下T 行每行包含三个正整数y、z、p，描述一个询问。
Output
输出文件calc.out 包括T 行.
对于每个询问，输出一行答案。
对于询问类型2 和3，如果不存在满足条件的，则输出“Orz, I cannot find x!”。
Sample Input#1
3 1
2 1 3
2 2 3
2 3 3
Sample Output#1
2
1
2
Sample Input#2
3 2
2 1 3
2 2 3
2 3 3
Sample Output#2
2
1
0
Sample Input#3
4 3
2 1 3
2 2 3
2 3 3
2 4 3
Sample Output#3
0
1
Orz, I cannot find x!
0
Hint
对于20%的数据，K=1
对于35%的数据，K=2
对于45%的数据，K=3
对于100%的数据，\(为质数1 \leq y,z,P \leq 10^9 ,P为质数,1 \leq T \leq 10\).
Solution
对于K=1 快速幂即可。
对于K=2 移项得$x \equiv \frac{z}{y}\ (mod\ p) \Rightarrow x \equiv zy^{-1}\ (mod\ p) $求逆元即可。
对于K=3，bsgs即可。
介绍一下包身工树(Baby steps Giant steps):
根据欧拉定理，答案显然不超过\(\varphi(p)\) ,即\(p-1\).
考虑分块作答，确定一个阈值K，设x=aK+b,那么\(y^{aK+b} \equiv z\ (mod \ p) \Leftrightarrow y^{ak} \equiv zy^{-b}\ (mod\ p)\)
显然\(b\)的取值只有k种，\(a\)的取值只有\(p/k\)种，预处理出同余式右边，扔到数据结构维护一下，然后枚举左边check计算即可，记得优先保证答案最小。bsgs的优化：上述是要求逆元的，事实上，将\(x\)设为\(aK-b\)就可以巧妙的避免逆元了。显然在\(K=\sqrt {\varphi(p)}\) 时，时间复杂度最优。
Code
#include <stdio.h>
#include <math.h>
#include <map>
#define R register
#define ll long long
inline int read(){
R int x; R bool f; R char c;
for (f=0; (c=getchar())<'0'||c>'9'; f=c=='-');
for (x=c-'0'; (c=getchar())>='0'&&c<='9'; x=(x<<1)+(x<<3)+c-'0');
return f?-x:x;
}
int T,tp,y,z,p;
std::map<int,int> mp;
inline int pw(int x,int k,int p){
R int res=1;
for (; k; k>>=1,x=(ll)x*x%p) if (k&1) res=(ll)res*x%p;
return res;
}
inline void bsgs(int y,int z,int p){
if (y==0&&z==0) return (void)(puts("1"));
if (y==0) return (void)(puts("Orz, I cannot find x!"));
R int m=sqrt(p)+0.5;mp.clear();R int tmp=0;for (R int i=0; i<=m; ++i){
if (i==0) {tmp=z%p; mp[tmp]=0; continue;}
tmp=(ll)tmp*y%p;
mp[tmp]=i;
}R int t=pw(y,m,p);tmp=1;
for (R int i=1; i<=m; ++i){
tmp=(ll)tmp*t%p;
if (mp.count(tmp)){
R ll ans=((ll)i*m)-mp[tmp];
ans=(ans%p+p)%p;
printf("%lld\n",ans);
return;
}
}puts("Orz, I cannot find x!");return;
}
int main(){
T=read(),tp=read();
while(T--){
y=read(),z=read(),p=read();y%=p;
if (tp==1) printf("%d\n",pw(y,z,p));
else if (tp==2){
z%=p;if (y==0&&z!=0) puts("Orz, I cannot find x!");
else printf("%lld\n",(ll)z*pw(y,p-2,p)%p);
}else bsgs(y,z,p);
}
}
