# $$\huge\texttt{去}_{\small\texttt{萌}^{\large\texttt{的}}}^{\large\texttt{你}_{\small\texttt{新}}}$$
`# $$\huge\texttt{去}_{\small\texttt{萌}^{\large\texttt{的}}}^{\large\texttt{你}_{\small\texttt{新}}}$$`
by t162 @ 2019-03-17 14:11:22
紫题简单，orz，tql
by 塔罗兰 @ 2019-03-17 14:11:59
Orz bsgs水题 Orz
by Sai0511 @ 2019-03-17 14:13:45
@[Sai_0511](/space/show?uid=114320) orz某神仙学校大佬
by 樱初音斗橡皮 @ 2019-03-17 14:18:35
emmm
by xiaolou @ 2019-03-17 14:20:51
@[樱初音斗橡皮](/space/show?uid=66287) ???我学校什么时候成神仙学校了...明明是个菜鸡学校Orz
by Sai0511 @ 2019-03-17 14:24:40
@[Sai_0511](/space/show?uid=114320) 侮辱学校，举报了（雾）
by 樱初音斗橡皮 @ 2019-03-17 14:25:14
@[樱初音斗橡皮](/space/show?uid=66287)
这题龟速乘常数太大了，未必能卡过去，可以尝试一下用__int128代替。。
by Sai0511 @ 2019-03-17 14:30:46
@[Sai_0511](/space/show?uid=114320) 不是，我的意思是结论是错的
by 樱初音斗橡皮 @ 2019-03-17 14:32:15
```cpp
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define il inline
#define gc getchar
#define pc putchar
typedef __int128 int64;
typedef double D;
typedef long long LL;
using namespace std;
int64 n,m,i,j,k;
struct io{
il int64 read(){
int64 x=0;bool f=0;char c;
for(c=gc();!isdigit(c);c=gc()) f|=c=='-';
for(;isdigit(c);c=gc()) x=(x<<1)+(x<<3)+(c^48);
return x;
}
il void write(int64 x){
bool FF=0;stack<int>sk;while(!sk.empty()) sk.pop();
if(x<0) FF=1,x=-x;if(!x){pc('0');return;}
while(x) sk.push(x%10),x/=10;if(FF) sk.push('-'-48);
while(!sk.empty()) pc(sk.top()+48),sk.pop();
return;
}
il void writeln(int64 x){
write(x);pc('\n');
}
}Fio;
#define read Fio.read
#define write Fio.write
#define writeln Fio.writeln
il int64 fpow(int64 a,int64 b,int64 mod){
int64 ans=1,base=a;
while(b){
if(b&1) ans=(ans%mod*base%mod)%mod;
base=(base*base)%mod;b>>=1;
}
return ans;
}
il int64 bsgs(int64 a,int64 b,int64 qmod){
map<int64,int64> Map;Map.clear();
b%=qmod; int64 block=sqrt((D)qmod)+1;
int64 i,tmp;
for(i=0;i<block;i++){
tmp=b*fpow(a,i,qmod)%qmod;
Map[tmp]=i;
}
a=fpow(a,block,qmod);if(!a) return !b?1:-1;
for(i=0;i<=block;i++){
tmp=fpow(a,i,qmod);
int64 tmp2=Map.find(tmp)==Map.end()?-1:Map[tmp];
if(tmp2>=0&&i*block-tmp2>=0) return i*block-tmp2;
}
return -1;
}
int main(){
k=read();m=read();
/* (10^n-1)/9 = k(mod m)
10^n-1 = 9k(mod m)
10^n = 9k+1(mod m)
Ans = bsgs(10,9k+1,m) */
int64 a=10,b=9*k+1,c=m,tmp=bsgs(a,b%m,c);
writeln(tmp);
}
```
几个月前写的，码风有点丑。
太久不写bsgs了，都快忘光了）
by Sai0511 @ 2019-03-17 14:34:47