本文共 1289 字，大约阅读时间需要 4 分钟。
【题目链接】
【题目大意】
计算满足 Y^x ≡ Z ( mod P) 的最小非负整数
【题解】
BSGS裸题。
【代码】
#include #include #include #include #include using namespace std::tr1;using namespace std;typedef long long ll;typedef pair P;int phi(int n){ int t=1,i; for(i=2;i*i<=n;i++)if(n%i==0)for(n/=i,t*=i-1;n%i==0;n/=i,t*=i); if(n>1)t*=n-1; return t;}int pow(ll a,int b,int m){ll t=1;for(;b;b>>=1,a=a*a%m)if(b&1)t=t*a%m;return t;}int gcd(int a,int b){return b?gcd(b,a%b):a;}int exgcd(int a,int b,int&x,int&y){ if(!b)return x=1,y=0,a; int d=exgcd(b,a%b,x,y),t=x; return x=y,y=t-a/b*y,d;}int bsgs(int a,int r,int m){ if(r>=m)return -1; int i,g,x,c=0,at=int(2+sqrt(m)); for(i=0,x=1%m;i<50;i++,x=ll(x)*a%m)if(x==r)return i; for(g=x=1;__gcd(int(ll(x)*a%m),m)!=g;c++)g=__gcd(x=ll(x)*a%m,m); if(r%g)return -1; if(x==r)return c; unordered_map u; g=phi(m/g),u[x]=0;g=pow(a,g-at%g,m); for(i=1;i ::iterator t=u.find(r=ll(r)*g%m); if(t!=u.end())return c+i*at+t->second; }return -1;}void solve(int y,int z,int p){ y%=p; z%=p; int t=bsgs(y,z,p); if(t==-1){puts("no solution");return;} else printf("%d\n",t);}int main(){ int a,b,c; while(~scanf("%d%d%d",&a,&b,&c))solve(b,c,a); return 0;}
转载于:https://www.cnblogs.com/forever97/p/bzoj3239.html