洛谷P4884 - 多少个1?

被浏览

我们通过观察可以发现 $11\cdots1$ 可以变化为 $\frac{10^{n}-1}{9}$,于是根据取模的性质,我们可以把原式两边同乘九再加一、原式变为 $10^{n} \equiv k \cdot 9 + 1 \pmod m$,发现这是个 BSGS 的标准式子,由于$m$保证为质数,所以也不必用拓展 BSGS。

然后愉快地交了一发,发现只有 80 分。再看一眼数据范围——中间过程相乘会爆$long\;long$,所以我们需要快速乘来防止溢出。然而丧心病狂的出题人卡 $log_{n}$的快速乘,所以我们需要复杂度更优常数更小的快速乘:

1
2
3
4
5
6
7
// 传说中复杂度更优的O(1)快速乘
// 参考链接:https://zhuanlan.zhihu.com/p/31872064
LL mul(LL a, LL b, LL P) {
LL L = a * (b >> 25LL) % P * (1LL << 25) % P;
LL R = a * (b & ((1LL << 25) - 1)) % P;
return (L + R) % P;
}

看着这么高级其实就是利用了小学生都会的乘法分配律。

我们要计算 $a \cdot b\;mod\;p$,设 $b=L+R$。

那么原式就变为 $a\cdot(L+R)\;mod\;p=((a\cdot L)\;mod\;p+(a\cdot R)\;mod\;p)\;mod\;p$。

我们把 $L$ 钦定为 $b$ 的二进制前 $x$ 位,$R$ 为 $b$ 的后 $(64-x)$ 位。

就得到了以上的代码(以上这份代码 $x=25$)。

用上这样的快速乘就可以 AC 了。

以下为代码:

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
#include <cmath>
#include <cstdio>
#include <iostream>
#include <unordered_map>
using namespace std;
typedef long long LL;
LL k, m;
// C++11标准及以上的哈希表unordered_map
unordered_map<LL, LL> Hash;
LL mul(LL a, LL b, LL P) {
LL L = a * (b >> 25LL) % P * (1LL << 25) % P;
LL R = a * (b & ((1LL << 25) - 1)) % P;
return (L + R) % P;
}
LL pw(LL a, LL n, LL P) {
LL ans = 1;
while (n) {
if (n & 1) ans = mul(ans, a, P);
a = mul(a, a, P);
n >>= 1;
}
return ans;
}
LL BSGS(LL a, LL b, LL P) {
LL len = ceil(sqrt(P));
for (LL i = 0; i < len; i++) Hash[mul(b, pw(a, i, P), P)] = i;
a = pw(a, len, P);
for (LL i = 0; i <= len; i++) {
LL x = pw(a, i, P);
LL j = Hash.count(x) ? Hash[x] : -1;
if (j >= 0 && i * len - j >= 0) return i * len - j;
}
return -1;
}
int main() {
scanf("%lld%lld", &k, &m);
k = k * 9 + 1;
k %= m;
printf("%lld", BSGS(10, k, m));
}