【CF913G】Power Substring
题意：T组询问，每次给定一个数a，让你求一个k，满足$2^k$的10进制的后$min(100,length(k))$位包含a作为它的子串。你只需要输出一个k，不需要最小化k的值，保证有解。
$Tle 2000，ale 10^{11}$
题解：神题。
假设a有n位，$2^k=x$，$x=a imes 10^m+b(mod 10^{n+m})$，我们显然有$kge n+m$，所以$2^{n+m}mid x$，又因为$2^{n+m}mid 10^{n+m}$，则$2^{n+m}mid a imes 10^m+b$（等式1）。因为$5^{n+m} mid x$，$5^{n+m}mid 10^{n+m}$，所以$5^{n+m} mid a imes 10^m+b$（等式2）。当m确定时，b的取值范围就是一段连续的、长度为$10^m$的区间，所以当$10^mge 2^{n+m}$时一定有解，所以m不会太大，我们考虑枚举m。
当m确定时，我们可以根据上面那两条等式快速求出b的值，但如何根据b的值反推得到x的值呢？我们发现等式1的左右两端都能被$2^{n+m}$整除，所以将其除以$2^{n+m}$，得到$y=w (mod 5^{n+m}),w=frac {a imes 10^m+b} {2^{n+m}}$。容易证明如下引理：
引理：对于任意$mle 1$，2是$5^m$的原根。
证明：首先通过枚举可知2是5的原根，$2^i=2,4,3,1,2,....$，循环节为4。
熟悉原根的都知道，a是p的原根当且仅当：将$varphi(p)$分解质因数变成$prod p_i^{e_i}$后，对于任意的i，$a^{frac {varphi(p)} {p_i}} eq 1 (mod p)$。那么当$mge 2$时，$varphi(5^m)$分解质因数形式为$2^2 imes 5^{m-1}$，有$2^{4 imes 5^{m-2}}=(2^{5^{m-2}})^4=2^4(mod p^2)$，且$2^{2 imes 5^{m-1}}=2^2(mod p^2)$，二者在$mod p^a$意义下显然不为1。所以2是$p^m$的原根。
现在我们只需要求出$w$的指标就好了，这里求指标的方法采用了归纳的思想：
1.我们先暴力求出$w$在$mod 5$意义下的指标$d_1$。
2.我们希望从w在$mod 5^m$意义下的指标$d_m$推导出w在$mod 5^{m+1}$意义下的指标$d_{m+1}$，发现对于$jin{0,1,2,3,4}$，存在唯一的j使得$2^{d_m+j}=1(mod 5^{m+1})$。所以我们暴力枚举j即可。
注意最后这一步采用快速幂会爆long long，所以还要用快速乘。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int T,n,m;
ll x,y,a,b;
inline ll ps(ll x,ll y,ll P)
{
ll z=0;
while(y)
{
if(y&1) z=z+x;
x<<=1,y>>=1;
if(x>=P) x-=P;
if(z>=P) z-=P;
}
return z;
}
inline ll pm(ll x,ll y,ll P)
{
ll z=1;
x%=P;
while(y)
{
if(y&1) z=ps(z,x,P);
x=ps(x,x,P),y>>=1;
}
return z;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%lld",&a);
ll t=a,m1=1;
n=0;
while(t) t/=10,n++;
for(m=0;;m++,a*=10,m1*=10)
{
b=(-a)&((1<<(n+m))-1);
if((a+b)%5==0) b+=1<<(n+m);
if(b>=m1) continue;
x=a+b,y=x>>(n+m);
int i,j;
ll now=0,phi,pw;
for(i=0;i<4;i++) if(pm(2,i,5)==y%5) now=i;
phi=4,pw=5;
for(i=2;i<=n+m;i++)
{
pw*=5;
for(j=0;j<5;j++) if(pm(2,now+j*phi,pw)==y%pw)
{
now+=j*phi;
break;
}
phi*=5;
}
printf("%lld
",now+n+m);
break;
}
}
return 0;
}//1 5