Power Substring

题目传送门

考虑求$a * 10 ^ {m} + x \equiv 2 ^ {k} \% 10 ^ {n + m}$,$n$是$a$在十进制下的位数
然后考虑中国剩余定理,先求一个满足$a*10^{m}+x \equiv 2^{k} \% 2^{n+m}$的解
令$k > n + m,y = (a*10^{m}+x) \% 2^{n + m} + i * 2^{n + m}$,
因为对于$2^{k} \% 5^{n+m}$来说,$2$是模数的一个原根,只要保证$y \% 5 != 0$就可以保证存在$k$满足所有等式
然后转为求$(y / 2^{n + m}) \equiv 2 ^{k} \% 5 ^ {n + m}$的$k$的值
然后有个公式可以优化:
若$a ^ {k} \equiv c \% p^{i}$
则存在$0 \leq j \leq p - 1$满足$a ^ {k + j * \varphi(p^{i})} \equiv c \% p^{i+1}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
//created by missever
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const int maxn = 1e5 + 5;
LL mod;
LL add(LL x, LL y) {
x += y;
if(x >= mod) x -= mod;
return x;
}
LL mul(LL a, LL b) {
LL r = (a * b - (LL)(((long double)a * b) / mod) * mod);
return add(r - r / mod * mod, mod);
}
LL powt(LL a,LL b) {
LL r = 1;
while(b >= 1) {
if(b & 1) r = mul(r,a);
a = mul(a,a);
b >>= 1;
}
return r;
}
int f[] = { -1, 0, 1, 3, 2};
int main() {
#ifdef CX_TEST
freopen("E:\\program--GG\\test_in.txt", "r", stdin);
#endif
int t, n, m, i;
LL a, b, x, k, phi;
scanf("%d", &t);
while(t--) {
scanf("%lld", &a);
n = to_string(a).size();
for(m = 0, b = 1; 1; m++, a *= 10, b *= 10) {
x = a;
mod = 1LL << (n + m);
if(x % mod) x += mod - x % mod;
if(x % 5 == 0) x += mod;
if(x % mod == 0 && x % 5 && x - a < b) {
x >>= n + m;
k = f[x % 5];
for(i = 1,phi = 4,mod = 25; i < n + m; i++,mod *= 5,phi *= 5) {
while(powt(2,k) != x % mod) k += phi;
}
printf("%lld\n",n + m + k);
break;
}
}
}
return 0;
}