- #include<map>
- #include<cmath>
- #include<cstdio>
- using namespace std;
- int y,z,p;
- map<int,int>mp;
- int Pow(int a,int b,int m)
- {
- int ans=1;
- for(;b;a=1LL*a*a%m,b>>=1)
- if(b&1) ans=1LL*ans*a%m;
- return ans;
- }
- int gcd(int a,int b) { return !b ? a : gcd(b,a%b); }
- void exgcd(int a,int b,long long &x,long long &y)
- {
- if(!b) { x=1; y=0; return; }
- exgcd(b,a%b,y,x); y-=a/b*x;
- }
- void bsgs()
- {
- mp.clear();
- int m=ceil(sqrt(p));
- int mul=z;
- //mp[z]=0;
- for(int j=1;j<=m;++j)
- {
- mul=1LL*y*mul%p;
- mp[mul]=j;
- }
- int am=Pow(y,m,p);
- mul=1;
- for(int j=1;j<=m;++j)
- {
- mul=1LL*mul*am%p;
- if(mp.find(mul)!=mp.end())
- {
- printf("%d\n",j*m-mp[mul]);
- return;
- }
- }
- puts("Orz, I cannot find x!");
- }
- int main()
- {
- int T,k;
- scanf("%d%d",&T,&k);
- if(k==1)
- while(T--)
- {
- scanf("%d%d%d",&y,&z,&p);
- printf("%d\n",Pow(y,z,p));
- }
- else if(k==2)
- {
- long long x0,y0;
- int g;
- while(T--)
- {
- scanf("%d%d%d",&y,&z,&p);
- g=gcd(y,p);
- if(z%g) puts("Orz, I cannot find x!");
- else
- {
- y/=g; p/=g;
- exgcd(y,p,x0,y0);
- x0=(x0%p+p)%p;
- x0=x0*z/g%p;
- printf("%lld\n",x0);
- }
- }
- }
- else
- while(T--)
- {
- scanf("%d%d%d",&y,&z,&p);
- if(!(y%p)) puts("Orz, I cannot find x!");
- else bsgs();
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2504950.html