题解：AT_agc070_a [AGC070A] Multiples in the String

· · 题解

目前的题解一篇乱搞一篇正解还有一篇是结论完全错误的东西（事实上对任意质数 p，\frac 1p 都是纯循环小数）。所以来补一个题解。

顺带一提这个题怎么是我四五个月前研究过的东西。

首先如果考虑拼接等等方法看起来就不是很行，我们希望找到一个空间利用率尽可能高的方法。有一个很知名的“走马灯数”，即 \frac{1}{7} 的循环节：a=142857，ia(1\leq i<7) 事实上遍历了 a 的每一种循环移位：

\begin{cases} 2\times 142857=285714\\ 3\times 142857=428571\\ 4\times 142857=571428\\ 5\times 142857=714285\\ 6\times 142857=857142\\ \end{cases}

那么只需要让 S=\textsf{142857142857} 就包含了 a 的六个倍数。

取分母 p=17 或 p=19，将 \frac 1p 的循环节 a 取出，此时 ia(1\leq i<p) 也同样遍历了 a 的所有循环移位。100 以内合法的数有 7,17,19,23,29,47,59,61,97。

那么如果我们找到一个合法的 p>1000，这道题就做完了：将 \frac 1p 的循环节在第一行输出一次去掉前导零作为 X，在第二行输出两次作为 S 就是一个符合要求的构造。

考虑怎么寻找合法的 p，条件显然就是 \frac 1p 的每个小于 1 的倍数都可以通过将 \frac 1p 的小数部分循环移位得到。对于小数部分循环移位我们显然会考虑乘以 10^k 然后模 1 去掉整数部分。于是对于每个 1\leq n<p 存在一个 m\geq 0 使得

10^mp^{-1}\equiv np^{-1}\pmod 1\iff 10^m\equiv n\pmod p

于是我们只需要枚举质数 p，并检验 10 是否是 p 的原根即可（这等价于 \frac 1p 的循环节长 p-1），暴力枚举发现 p=1019 是最小的大于 1000 的合法解。

最小的几个合法解是 1019,1021,1033,1051,1063,1069,1087,1091,1097。

事实上你可以在 \Omicron(v\log v) 的时间里检验所有 1\leq p\leq n。但是显然这没有什么用处。

Code.