正解:$BSGS$
解题报告:
首先看到这个若干个一,发现不好表示,考虑两遍同时乘九加一,于是变成$10^nequiv 9cdot K+1(mod m)$
昂然后不就是$bsgs$板子了嘛?太板子了不说了$kk$
$over$
然后说下,这个数据比较大,#8#9的都要$int128$或者龟速乘.
然后因为不知名原因全开$int128$会$CE$
最后我瞎选了几个数开$int128$过的,,,
#include<bits/stdc++.h> using namespace std; #define il inline #define lf double #define gc getchar() #define ll long long #define i128 __int128 #define ri register ll #define rb register bool #define rc register char #define rp(i,x,y) for(ri i=x;i<=y;++i) #define my(i,x,y) for(ri i=x;i>=y;--i) ll K,mod; map<i128,ll>M; il i128 read() { rc ch=gc;i128 x=0;rb y=1; while(ch!='-' && (ch>'9' || ch<'0'))ch=gc; if(ch=='-')ch=gc,y=0; while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc; return y?x:-x; } il i128 power(i128 x,i128 y){ri ret=1;while(y){if(y&1)ret=1ll*ret*x%mod;x=1ll*x*x%mod;y>>=1;}return ret;} il void BSGS(i128 x,i128 y) { i128 m=sqrt(mod)+1,t=y;rp(i,0,m-1)M[t]=i,t=1ll*t*x%mod; i128 tmp=power(x,m);t=tmp; rp(i,1,m){if(M.count(t)){printf("%lld ",1ll*i*m-M[t]);return;}t=1ll*t*tmp%mod;} } signed main() { //freopen("4884.in","r",stdin);freopen("4884.out","w",stdout); K=read();mod=read();BSGS(10,9*K+1); return 0; }