花了一下午时间透彻理解了BSGS的实现方法,感觉还可以,其实也没之前想的那么难。。。
BSGS是什么呢?—— 可以求解高次同余方程。简洁明了。
要是想学的话推荐一下这位大佬的博客,讲的还是很清晰明了的。
我们来说这道题。。。。。
我们通过观察可以发现 根据取模的性质,我们可以把原式两边同乘九再加一
发现这是个 BSGS 的标准式子,由于m保证为质数,所以也不必用拓展 BSGS。
同时我们发现这道题目是会爆LL的
大佬们都会写_int128 ,只好去学了个快速乘,啦啦啦
快速乘代码:
LL mul(LL a,LL b,LL p) { LL L=a*(b>>25LL)%p*(1LL<<25)%p; LL R=a*(b&((1LL<<25)-1))%p; return (L+R)%p; }
这样的话,这道题就可以A了,开心。
#include<bits/stdc++.h> using namespace std; #define LL long long LL k,P; LL mul(LL a,LL b,LL p) { LL L=a*(b>>25LL)%p*(1LL<<25)%p; LL R=a*(b&((1LL<<25)-1))%p; return (L+R)%p; } LL ksm(LL x,LL y) { LL res=1; for (;y;y>>=1,x=1LL*mul(x,x,P)) if (y&1)res=1LL*mul(res,x,P); return res; } map<LL,LL> mp; int main() { scanf("%lld%lld",&k,&P); k=9*k+1;k%=P; LL m=ceil(sqrt(P));LL now=k; for (LL i=0;i<=m;i++) { mp[now]=i+1; now=mul(now,10,P); } now=1;LL ans=-1;LL kk=ksm(10,m); for (LL i=1;i<=m;i++) { now=1LL*mul(now,kk,P); if (mp[now]) {ans=i*m-mp[now]+1;break;} } printf("%lld",ans); return 0; }