AtCoder Grand Contest 070 A問題メモ
としのせのせのせこしたんたん
A - Multiples in the String
問題文
- この問題は output-only です。入力は与えられません。
- 正整数 $X$ と文字列 $S$ の組 $(X, S)$ であって以下の条件を全て満たすものを $1$ つ挙げてください。
- $X$ は $10^{50}$ 以上 $10^{5000}$ 未満の正整数である。
- $S$ は 0 から 9 までの数字からなる長さ $5000$ 以下の文字列である。
- $1 \leq i \leq 1000$ を満たす整数 $i$ 全てに対して次の条件が成り立つ。
- $X$ を $i$ 倍した整数を $10$ 進表記して出来る文字列は $S$ の(連続な)部分文字列である。
解法
気がつけば一発な構築問題。
要求される知識は、雑学としてそこそこ有名ではあるが、競プロで使われるのは珍しめで気付くのに時間かかった。
その分、気がついたときは「なるほど！」と唸らされる問題。
はじめに陥った方針
$X=$'10002000400080016…' みたいに、桁を揃えて2の累乗数を連ねていけば、
$2$ の累乗倍に関してはずらすだけでいいな。。。とか考えていた。
こうすると、$5$ の累乗倍に関しても '50010002000400080…' と、元の $X$ の左側を拡張することで重ねられる。
が、それ以外の倍数は '300060012…'、'700140028…' みたいに、
結局、独自に50桁を消費して $S$ に埋め込まなければならない。
$1～1000$ の中で、$k \times 2^x 5^y$ と表されるような $k$ の種類の数だけ、独自に50桁（以上）を使う必要があるが、
そのような $k$ は400種類ほどあるため、とても $|S| \le 5000$ では無理。
もっと何か、全然別の発想が必要となる。
正しい方針
ふと、7の倍数は巡回することを思い出す。
142857 × 1 = 142857 142857 × 2 = 285714 142857 × 3 = 428571 142857 × 4 = 571428 142857 × 5 = 714285 142857 × 6 = 857142
仮に $X=142857, S=142857142857$ とすることで、$i=1～6$ の時には要件を満たす。
このような数が他にないか調べると、巡回数 に行き着く。
$\dfrac{1}{a}$ の小数の循環部分を取り出したものを $X$ とすると、 $X$ に $1～a-1$ をかけた数がいずれも $X$ を転回させたものとなるような特徴を持つ $a$ は、 A001913 - OEIS にまとめられている。（ページ冒頭では1000未満の数までしか掲載されていないが、中ほどにあるLINKSの “Table of n, a(n) for n = 1..10000” から続きを見られる）
$a \gt 1000$ を満たす、例えば $a=1019$ などとして $X$ を求め、それを2つ繋げたものを $S$ とすれば答えとなる。
$X$ を求めるのは、Pythonなど多倍長整数が可能な言語なら $\dfrac{10^{a-1}-1}{a}$ を計算すればよい。
補足1
何故このような綺麗な形になるのか？
これは、原始根と関係がある。
循環小数は、10倍したら当然、1桁ずれた形になる。循環する長さ分だけ繰り返したら、以降はループするので止める。
1/7 = 0.142857142857...
10/7 = 1.428571428571...
100/7 = 14.285714285714...
1000/7 = 142.857142857142...
10000/7 = 1428.571428571428...
100000/7 = 14285.714285714285...
ここから、右辺の整数部分にあたる数を両辺から引くと、左辺の分子には1～6が1回ずつ現れる。
1/7 = 0.142857142857... 3/7 = 0.428571428571... 2/7 = 0.285714285714... 6/7 = 0.857142857142... 4/7 = 0.571428571428... 5/7 = 0.714285714285...
循環部分を取り出して $x$ とすると、$x$ の $1～6$ 倍に、1桁ずつずれたものが1回ずつ現れる。
$x$ の7倍が $10^6$ 未満なので、7桁目に繰り上がることはない。
x = 142857 3x = 428571 2x = 285714 6x = 857142 4x = 571428 5x = 714285
$1,10,10^2,10^3,...,10^{a-2} \mod{a}$ に、$1～a-1$ が1回ずつ現れるような $a$ が、このような性質となる。
「$10$ を原始根として持つ1001以上の素数」を $a$ にすればよいことがわかる。
補足2
さらに、（手間が増えるので敢えて選択する意味はあまりないが）原始根や素数でなくてもよい。
たとえば $a=13$ は10を原始根として持たないが、$1/13～12/13$ は6桁を循環節とする2タイプに分けられる。
（巡回させて一致するものを「同じタイプ」とする）
循環節タイプ 01/13 = 0.076923076923 ① 076923 02/13 = 0.153846153846 :: ② 153846 03/13 = 0.230769230769 ① 230769 :: 04/13 = 0.307692307692 ① 307692 :: 05/13 = 0.384615384615 :: ② 384615 06/13 = 0.461538461538 :: ② 461538 07/13 = 0.538461538461 :: ② 538461 08/13 = 0.615384615384 :: ② 615384 09/13 = 0.692307692307 ① 692307 :: 10/13 = 0.769230769230 ① 769230 :: 11/13 = 0.846153846153 :: ② 846153 12/13 = 0.923076923076 ① 923076
なので、$X=76923$、$S=076923076923153846153846$ （2タイプの循環節をそれぞれ2回繰り返した文字列）とすると、$i=1～12$ に対して条件を満たす。
$a$ が $10$ と互いに素でない場合は循環小数の開始位置がずれるため上手くいかないが、
$10$ と互いに素な整数を $a$ とするといくつかのタイプの循環部分のグループに分けられる。
さらにそのタイプ毎の循環節の長さの和は $a-1$ となる性質がある。
ただ、10と互いに素なら何でも良いかというと、上手くいかない整数もある。
例えば分母として $a=1029(=3 \times 7^3)$ を考えると、$x/a$ を循環節の長さとタイプで分けると以下の通り。
- 294桁になる $x$ が3種882個
- 42桁になる $x$ が3種126個
- 6桁になる $x$ が3種18個
- 1桁になる $x$ が2種2個
この「循環節の長さ×タイプ数」の和は、$294 \times 3 + 42 \times 3 + 6 \times 3 + 1 \times 2 = 1028$ で、$a-1$ と等しくなる性質がある。
よって、もし「単純に各循環節を2回ずつ繰り返した文字列を結合したものを $S$ とする」なら、$a \le 2500$ に対して $S \le 5000$ が保証される。
だがこの問題では、循環節が6桁や1桁のものも、$S$ に含める際には最大のものに合わせて294桁にしないといけない。
たとえば $147/1029 = 0.142857142857...$ より6桁で循環するが、 $X$ を $1/1029$ の循環節にあわせて294桁とする場合、 $147X$ を $S$ に含める文字列も「142857142857…(294桁)」と、繰り返したものにしなければならない。
よって、$S$ に必要な長さは「循環節の『最大長さ』 × 全ての循環節のタイプ数」の2倍となり、必ずしも $a$ に比例しなくなる。
$a \le 2500$ であっても、必ずしも $|S| \le 5000$ に収まるとは限らなくなる。
$a=1029$ の例では、$294 \times 11 \times 2 = 5184$ で、制約を超えてしまう。
