好一道三合一...(然而被我做成了四合一)
其实1 2 3是独立的OvO
然后就可以逐个分析了...
1
快速幂..就不说了..(我省选的时候有这么水的20pts部分分么←_←
2
两种做法(写在标题里面了)..
2.1(扩展欧几里得)
(xyequiv z(mod p))
很显然可以写成(xy=np+z), 移项得(xy-np=z)
为保证(y,p)互质, 我们让两边同除(gcd(y,p)), 也就是让(y,p,z)分别除(gcd(y,p))
由扩展欧几里得, 如果(gcd(y,p))不能整除(z),那么方程无解...
处理完直接exgcd就行了.. 这样我们就能得到(xy-np=1)的解了.. 然后再乘个(z)后对p取模即可..
如果结果小于0呢? 我们可以(+z),一直加到不再小于0
或者是可以用(p-(-p) mod b)这样的方式来处理...
2.2(费马小定理)
嘛,其实有一个更简单的角度OvO
(xyequiv z(mod) (p)) ∴(x=y^{-1}*z)
所以我们求个逆元就完了OvO 由于(p)是质数, 而(y)一定不是(p)的倍数所以一定互质...
直接(x=z*y^{p-2})就做完了...
3
BSGS板子...
BSGS算法 原名Baby steps Giant steps算法 又叫大步小步、北上广深、拔山盖世算法...
就是专门用来求对于给定(y,z),满足(y^xequiv z(mod p))中的最小的x的方法...
其思路如下:
- 令(x=i*m-j)(这里写成减号方便移项), 则(y^{im-j}equiv z(mod p))
- 移项, (y^{im}equiv z*y^j(mod p))
然后我们枚举(i,j)即可...
这里的(m)我们取(left lceil sqrt p ight ceil)(可能是跟均值不等式有什么不可告人的关系吧??我也不知道)
之后先从(0sim m)枚举(j) ,将(z*y^j)存到表里...(开map大概就可以了OvO, 记得值相同就覆盖掉, 因为要求(im-j)的最小值, 所以要让(j)尽量大...)
然后从(1sim m)枚举(i) ,如果(y^{im})在表里找到了相等的值, 那就找到了(x), 而且(x)肯定是最小的..
这样就行了..具体实现可以看代码
代码
今天心情特别好, 所以写代码要压行... 然后这个三合一写了15行OvO
所以就出现了很难看的代码OvO...建议学习代码实现的还是去百度另寻高明吧OvO
#include <map>
#include <cmath>
#include <cstdio>
typedef long long LL;
std::map<LL,int> v;LL T,L,y,z,c;
#define NOANS {puts("Orz, I cannot find x!");return;}
inline LL gn(LL a=0,char c=0){for(;c<48||c>57;c=getchar());for(;c>47&&c<58;c=getchar())a=a*10+c-48;return a;}
LL qpow(LL a,LL b,LL p,LL s=1){for(;b;b>>=1,a=a*a%p)if(b&1) s=s*a%p;return s;}
void B(){y%=c;z%=c;if(z&&!y)NOANS printf("%d
",z*qpow(y,c-2,c)%c);} //这里用的费马(因为短)
void C(LL m=1,LL x=1,LL p=1){if(y%c==0)NOANS m=sqrt(c)+0.5;x=z;p=qpow(y,m,c);v.clear();
for(LL j=0;j<=m;++j)v[x]=j,x=x*y%c;x=1;
for(LL i=1;i<=m;++i){x=x*p%c;if(v[x]){printf("%lld
",i*m-v[x]);return;}}
NOANS} //BSGS
void WORK(){T=gn(),L=gn();while(T--){y=gn(),z=gn(),c=gn();if(L==1)printf("%d
",qpow(y,z,c));if(L==2)B();if(L==3)C();}}
int main(){WORK();}
//LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);}
//void exgcd(LL a,LL b,LL& x,LL& y){!b?x=1,y=0:(exgcd(b,a%b,y,x),y-=(a/b)*x);}
//void B(LL a=0,LL b=0,LL d=0,LL x=0){a=y;b=-c;d=gcd(a,b);if(z%d)NOANS
// a/=d;b/=d;z/=d;exgcd(a,b,x,y);x=x*z%b;if(x<0)x=b-(-x)%b;printf("%d
",x);
//} //被注释的几行是2.1(扩欧的实现)