noip级数论模版题了吧。
让求三个东西：
- 给定y,z,p,计算`Y^Z Mod P` 的值。
- 给定y,z,p，计算满足`xy≡ Z ( mod P )`的最小非负整数。
- 给定y,z,p，计算满足`Y^x ≡ Z ( mod P)`的最小非负整数。
其中P均为素数。
来分着处理。
1 `y^z%p` 快速幂。
推荐一种又快又好写的写法。
LL power_mod(LL a,LL b,LL p){ //get a^b%p
LL ret=;
while(b){
) ret = ret * a % p;
a = a * a % p;
b>>=;
}
return ret;
}
为什么是对的呢，拆成二进制看一看就好了。
2 Yx==Z%p 扩展欧几里德。
Yx==Z%p可以变形成为Yx+py==Z
显然仅当gcd(Y,p)|Z时有解。
我们知道ex_gcd可以求ax0+by0==gcd(a,b)的一组解。
所以我们让原方程两边都除以gcd(Y,p)，然后得到Yx0+py0==gcd(Y,p)的一组解。
于是Z/gcd(Y,p)*x0%p为原题的答案。注意要让结果为正。
3 Y^x %p ≡ Z Baby step-giant step
其实也是一种分块的思想。
设 m=√p。
可以表示为 Y^(km) * Y^r == Z (mod P)。
注意到0<=r<m 只有√p种取值，所以我们可以预处理出来，算出它的逆元再乘Z，扔进一个set。
然后枚举k，set中查询Y^(km)，如果有这个值，就说明找到了解。
逆元的话。因为p是素数，所以直接power_mod(Y,p-2,p);就好了。
从原博客搬运过来。