洛谷P4884 - 多少个1？

 OI / 洛谷
被浏览 次

我们通过观察可以发现 $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));
}
 上一页