Luogu

算法

首先，我们可以把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。

和yyb一起学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;
}