簽到一臉
$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
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 }