luogu 4884 多少个1 (BSGS)

很有意思的一个签到题然而考场上并没有切掉

$1111...111=K(mod\;m)$

$10^{x}=9K+1(mod\;m)$

用$BSGS$求解即可

模数爆了$int$，需要快速乘，然而模数是$10^{11}$级别并不是特别大，可以利用位运算进行$O(1)$快速乘

 #include <cmath>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define N1 4000010

 #define M1 400010

 #define ll long long

 #define dd double

 #define cll const long long

 #define inf 23333333333333333ll

 using namespace std;

 ll K,M,A;

 struct Hsh{

 #define maxn 4000000

 int head[N1],nxt[M1],val[M1],cte;ll to[M1];

 void ins(ll x,int w)

 {

     int u=x%maxn; ll v;

     for(int j=head[u];j;j=nxt[j])

     {

         v=to[j];

         if(v==x) return;

     }

     cte++; to[cte]=x; nxt[cte]=head[u];

     val[cte]=w; head[u]=cte;

 }

 int find(ll x)

 {

     int u=x%maxn; ll v;

     for(int j=head[u];j;j=nxt[j])

     {

         v=to[j];

         if(v==x) return val[j];

     }

     return -;

 }

 }h;

 inline ll qmul(ll a,ll b){

     return ((((a>>)*b%M)<<)%M+(a&((<<)-))*b%M)%M;

 }

 ll qpow(ll x,ll y)

 {

     ll ans=;

     while(y){

         if(y&) ans=qmul(ans,x);

         x=qmul(x,x); y>>=;

     }return ans;

 }

 int main()

 {

     scanf("%lld%lld",&K,&M);

     A=(9ll*K+)%M;

     ll sq=sqrt(M),i,pw,now,ans;

     for(pw=qpow(10ll,sq),now=,i=;(i-)*sq<M;i++)

     {

         now=qmul(now,pw);

         h.ins(now,i);

     }

     for(now=A,ans=inf,i=;i<sq;i++)

     {

         pw=h.find(now);

         if(pw!=-) ans=min(ans,pw*sq-i);

         now=qmul(now,10ll);

     }

     printf("%lld\n",ans);

     return ;

 }

巴特西

luogu 4884 多少个1 (BSGS)

最新文章

热门文章