模数好大……__int128好麻烦……而且BSGS第一次写有点写蒙了……
$11...1(N个1)\equiv k(mod m)$很难算，那么考虑转化一下
先把$11...1(N个1)$写成$\frac{10^n-1}{9}$
则$$\frac{10^n-1}{9}\equiv k(mod m)$$
$$10^n-1\equiv k*9(mod m)$$
$$10^n\equiv k*9+1(mod m)$$
然后直接套上BSGS的板子
然后因为模数是long long级别的，所以要么用龟速乘，要么像我一样懒得只会用__int128了（记得手打输入输出）
1 //minamoto 2 #include<bits/stdc++.h> 3 using namespace std; 4 #define int __int128 5 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 6 char buf[1<<21],*p1=buf,*p2=buf; 7 inline int read(){ 8 #define num ch-‘0‘ 9 char ch;bool flag=0;int res; 10 while(!isdigit(ch=getc())) 11 (ch==‘-‘)&&(flag=true); 12 for(res=num;isdigit(ch=getc());res=res*10+num); 13 (flag)&&(res=-res); 14 #undef num 15 return res; 16 } 17 inline void print(int x) { 18 int sta[30],top=0; 19 while (x) sta[++top]=x%10,x/=10; 20 while (top) putchar(sta[top--]+‘0‘); 21 } 22 23 24 inline int BSGS(int a,int b,int p){ 25 map<int,int> mp;mp.clear(); 26 b%=p;int t=sqrt((double)p)+1,tot=1; 27 for(int j=0;j<t;++j){ 28 int val=b*tot%p; 29 mp[val]=j,tot=tot*a%p; 30 } 31 if(!tot) return b==0?1:-1; 32 a=tot,tot=1; 33 for(int i=0;i<=t;++i){ 34 int j=mp.find(tot)==mp.end()?-1:mp[tot]; 35 if(j>=0&&i*t-j>=0) return i*t-j; 36 tot=tot*a%p; 37 } 38 return -1; 39 } 40 signed main(){ 41 // freopen("testdata.in","r",stdin); 42 int k=read(),m=read(),ans=BSGS(10,(9*k+1)%m,m); 43 print(ans); 44 return 0; 45 }
原文：https://www.cnblogs.com/bztMinamoto/p/9740439.html