luoguU38228 签到题 (BSGS)

签到一脸

$a_n=10a_{n-1}+1$求出通项$a_n=frac{10^n-1}{9}$，然后可以化成$10^n=

$然后我们设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就可以了$

要写快速模乘、要开longlong

 1 #include<bits/stdc++.h>
 2 #define pa pair<int,int>
 3 #define ll long long
 4 using namespace std;
 5 const int maxn=1;
 6 
 7 inline ll rd(){
 8     ll x=0;char c=getchar();int neg=1;
 9     while(c<'0'||c>'9'){if(c=='-') neg=-1;c=getchar();}
10     while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
11     return x*neg;
12 }
13 
14 map<ll,ll> mp;
15 ll K,M,SM;
16 
17 inline ll modx(ll a,ll b){
18     ll re=0;
19     while(b){
20         if(b&1) re=(re+a)%M;
21         a=(a<<1)%M,b>>=1;
22     }return re;
23 }
24 
25 inline ll modp(ll a,ll p){
26     ll re=1;
27     while(p){
28         if(p&1) re=modx(re,a);
29         a=modx(a,a),p>>=1;
30     }return re;
31 }
32 
33 int main(){
34     ll i,j,k;
35     K=rd();M=rd();SM=ceil(sqrt(1.0*M));
36     ll b=(9*K+1)%M,x=1;
37     for(i=0;i<SM;i++,x=modx(x,10)) mp[modx(x,b)]=i;
38     ll y=x;
39     for(i=SM;;i+=SM,y=modx(y,x)){
40         if(mp[y]){
41             printf("%lld
",i-mp[y]);break;
42         }
43     }
44     return 0;
45 }