luoguU38228 签到题 (BSGS)

签到一脸

$a_n=10a_{n-1}+1$求出通项$a_n=\frac{10^n-1}{9}$，然后可以化成$10^n=9K+1 (mod m)$，求一个最小的n

然后我们知道这个n一定是<=m的

然后我们设n=i*t-j,其中$t=ceil(\sqrt{m})$,0<=i,j<t，移项，变成$10^{i*t}=(9K+1)*10^j$

我们把每个可能的$(9K+1)*10^j$都存下来（用hash或map），然后再枚举i去找和$10^{i*t}$相等的最大的j就可以了

复杂度基本上是$O(\sqrt{M}logM)$的

要写快速模乘、要开longlong

 #include<bits/stdc++.h>

 #define pa pair<int,int>

 #define ll long long

 using namespace std;

 const int maxn=;

 inline ll rd(){

     ll x=;char c=getchar();int neg=;

     while(c<''||c>''){if(c=='-') neg=-;c=getchar();}

     while(c>=''&&c<='') x=x*+c-'',c=getchar();

     return x*neg;

 }

 map<ll,ll> mp;

 ll K,M,SM;

 inline ll modx(ll a,ll b){

     ll re=;

     while(b){

         if(b&) re=(re+a)%M;

         a=(a<<)%M,b>>=;

     }return re;

 }

 inline ll modp(ll a,ll p){

     ll re=;

     while(p){

         if(p&) re=modx(re,a);

         a=modx(a,a),p>>=;

     }return re;

 }

 int main(){

     ll i,j,k;

     K=rd();M=rd();SM=ceil(sqrt(1.0*M));

     ll b=(*K+)%M,x=;

     for(i=;i<SM;i++,x=modx(x,)) mp[modx(x,b)]=i;

     ll y=x;

     for(i=SM;;i+=SM,y=modx(y,x)){

         if(mp[y]){

             printf("%lld\n",i-mp[y]);break;

         }

     }

     return ;

 }

巴特西

luoguU38228 签到题 (BSGS)

最新文章

热门文章