本文共 1275 字，大约阅读时间需要 4 分钟。
题解：
将原式处理成A^x≡B(mode C)的形式即可。
代码：
#include#include #include #include #include using namespace std;#define ll long longll fastpow(ll x,ll y,ll p){ ll ret = 1ll; while(y) { if(y&1)ret=ret*x%p; x=x*x%p; y>>=1; } return ret;}ll F2(ll y,ll z,ll p){ y%=p,z%=p; ll ret = fastpow(y,p-2,p); return ret*z%p;}map mp;void BSGS(ll y,ll z,ll p){ y%=p,z%=p; if(!y&&z) { printf("-1\n"); return ; } mp.clear();mp[1]=0; ll now = 1;ll m = (ll)sqrt(p); for(ll i=1;i<=m;i++) { now=now*y%p; if(mp.find(now)==mp.end()) mp[now]=i; } ll u = 1; for(ll i=0;i<=m+2;i++) { ll tmp = F2(u,z,p); if(mp.find(tmp)!=mp.end()) { ll ans = mp[tmp]; printf("%lld\n",ans+i*m+1); return ; } u=u*now%p; } printf("-1\n");}ll T,p,a,b,x1,t;int main(){ scanf("%lld",&T); while(T--) { scanf("%lld%lld%lld%lld%lld",&p,&a,&b,&x1,&t); a%=p,b%=p; if(x1==t) { printf("1\n"); continue; } if(!a) { if(b==t)printf("2\n"); else printf("-1\n"); continue; } if(a==1) { if(!b&&t-x1) { printf("-1\n"); }else printf("%lld\n",F2(b,t-x1+p,p)+1); continue; } ll k = (ll)F2(a-1,b,p); BSGS(a,(t+k)*fastpow(x1+k,p-2,p),p); } return 0;}
转载于:https://www.cnblogs.com/LiGuanlin1124/p/10046068.html