算法
首先,我们可以把n个1写成$\frac{10^n-1}{9}$
然后这个式子就变成了
$\frac{10^n-1}{9}\equiv k \pmod m$
$10^n-1\equiv 9k \pmod m$
$10^n\equiv 9k+1 \pmod m$
然后注意到$m$是质数,所以可以套上BSGS。
但是$m$最大有$10^{11}$,大概会爆long long。
所以要用龟速乘。
但是我常数太大,龟速乘过不去后面两个点。
所以最后选择了__int128
,手写输入输出即可。
PS:(其实hash可以用pbds里的gp_hash_table
,但是我写的程序无限waiting)
代码
#include <bits/stdc++.h>
#define re register
typedef int mainint;
#define int __int128
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
return X*w;
}
inline void write(int x) {
int sta[30],top=0;
while (x) sta[++top]=x%10,x/=10;
while (top) putchar(sta[top--]+'0');
}
inline int FastPow(int a,int k,int p) {
re int ans=1;
while (k) {
if (k&1) (ans*=a)%=p;
(a*=a)%=p; k>>=1;
}
return ans;
}
inline int BSGS(int a,int b,int p) {
map<int,int> hash; hash.clear();
b%=p; int t=(int)sqrt((double)p)+1;
for (re int j=0;j<t;j++) {
int val=b*FastPow(a,j,p)%p;
hash[val]=j;
}
a=FastPow(a,t,p);
if (!a) return (b==0)?1:-1;
for (re int i=0;i<=t;i++) {
int val=FastPow(a,i,p);
int j=hash.find(val)==hash.end()?-1:hash[val];
if (j>=0&&i*t-j>=0) return i*t-j;
}
return -1;
}
mainint main() {
int k=read(),m=read();
int ans=BSGS(10,(9*k+1)%m,m);
write(ans);
return 0;
}