题解：AT_agc070_a [AGC070A] Multiples in the String

· · 题解

题解：AT_agc070_a [AGC070A] Multiples in the String

首先观察到 X 至少是 51 位数，对于每个 1\leq i\leq1000 都要能够在 S 中找到 X\cdot i，就意味着会有 >50\times1000=5\cdot10^4 个位置是被用到的，显然会有重叠。因此我们的目标是让重叠越多越好。

如何重叠会最多呢？这让我们想到经典的 X=142857，则此时 2X=285714,3X=428571,4X=571428,5X=714285,6X=857142，对于 1\leq i\leq6，所有的 X\cdot i 都是 142857 的一个循环移位，拥有最多的重叠，则用一个 S=142857142857 就能全部搞定。

于是我们要探查一下 142857 拥有此性质的内在原理。考虑竖式计算 1÷7 的过程，发现在每一位的时候关键的只有之前的位给我留下的余数。由于循环节大小 6=7-1，所有 1,2,3,4,5,6 在算到第六位之前都刚好出现一次。因此我们算 2÷7,3÷7,4÷7,5÷7,6÷7 的过程都是算 1÷7 过程的一个后缀，这就使得得到的结果是 1÷7 的后缀，只取之后六位，就有了该性质。

换句话说，我们想找一个数 Z，使得十进制下 1÷Z 的过程中包含了全部 0,1,2,3,\dots,Z-1 且是纯循环。即执行如下代码：

int x = 1;
while (true) {
  x = x * 10 % Z;
  if (x == 1)
    break;
}

的过程中，程序能在有限时间内结束且 x=0,1,2,3,\dots,Z-1 都恰好出现过一次，即 10 是 Z 的原根。或者说，我们要找一个足够大的数 Z>1000，满足纯循环小数 \frac{1}{Z} 的最小循环节为 Z-1。直接施展素数筛，找循环节时就找最小的 k 使得 k 个 9 拼接而成的数是 Z 的倍数则 k 是循环节（或用上面代码模拟），找到的最小的一个是 Z=1019，因此用从高位到低位逐位模拟竖式的方式计算 \frac{1}{1019}，得到一个循环节 X，S 则为两个 X 拼接在一起。

:::info[打表找 P 的代码]

#include <bits/stdc++.h>

using namespace std;

bool np[10001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for (int i = 2; i <= 10000; i++) {
        if (!np[i] && i > 1000) {
            int cnt = 1, now = 9;
            while (now) {
                cnt++;
                now = (now * 10 + 9) % i;
            }
            if (cnt == i - 1)
                cout << i << ':' << cnt << '\n';
        }
        for (int j = i + i; j <= 10000; j += i)
            np[j] = true;
    }
    return 0;
}

:::

:::success[AC code]

#include <bits/stdc++.h>

using namespace std;

constexpr int P = 1019;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<int> ans;
    int now = 1;
    for (int i = 1; i < P; i++) {
        now = now * 10;
        ans.push_back(now / P);
        now = now % P;
    }
    for (int i : ans)
        cout << i;
    cout << '\n';
    for (int i : ans)
        cout << i;
    for (int i : ans)
        cout << i;
    cout << '\n';
    return 0;
}

:::