本文共 930 字，大约阅读时间需要 3 分钟。
题目大意：给出$P,B,N$，求最小的正整数$L$，使$B^L\equiv N(mod\ P)$。
$BSGS$模板题。
#include #include #include #include #include #include #include #include #include #include #include #define ll long longusing namespace std;int T,k;ll y,z,p;ll G;map ind;ll quick(ll x,ll y,ll mod){ ll res=1ll; while(y) { if(y&1) { res=res*x%mod; } x=x*x%mod; y>>=1; } return res;}void solve(){ ll n=ceil(sqrt(p)); if(y%p==0&&z) { printf("no solution\n"); return ; } ind.clear(); ll sum=z%p; ind[sum]=0; for(ll i=1;i<=n;i++) { sum=sum*y; sum%=p; ind[sum]=i; } sum=quick(y,n,p); ll num=1ll; for(int i=1;i<=n;i++) { num*=sum,num%=p; if(ind.find(num)!=ind.end()) { printf("%lld\n",((n*i-ind[num])%p+p)%p); return ; } } printf("no solution\n");}int main(){ while(scanf("%lld%lld%lld",&p,&y,&z)!=EOF) { solve(); }}
转载于:https://www.cnblogs.com/Khada-Jhin/p/10625415.html