2.2 KiB
id, title, challengeType, forumTopicId, dashedName
| id | title | challengeType | forumTopicId | dashedName |
|---|---|---|---|---|
| 5900f45b1000cf542c50ff6d | 問題 238: 無限文字列ツアー | 5 | 301883 | problem-238-infinite-string-tour |
--description--
"Blum Blum Shub" 擬似乱数法により次の数列を作ります。
$$ s_0 = 14025256 \\ s_{n + 1} = {s_n}^2 \; mod \; 20\,300\,713 $$
これらの数 s_0s_1s_2\ldots を連結して、無限長の文字列 w を作成します。 したがって、w = 14025256741014958470038053646\ldots です。
正の整数 k について、各位の和が k に等しくなるような w の部分文字列が存在しない場合、p(k) を 0 とします。 各位の和が k に等しくなるような w の部分文字列が少なくとも 1 つ存在する場合、p(k) = z と定義します。ここで、z はそのような部分文字列のうち最も前にある部分文字列の先頭位置です。
例:
部分文字列 1, 14, 1402, … はそれぞれ各位の和が 1, 5, 7, …であり、位置 1 から始まります。したがって、p(1) = p(5) = p(7) = \ldots = 1 です。
部分文字列 4, 402, 4025, … はそれぞれ各位の和が 4, 6, 11, …であり、位置 2 から始まります。したがって、p(4) = p(6) = p(11) = \ldots = 2 です。
部分文字列 02, 0252, … はそれぞれ各位の和が 2, 9, …であり、位置 3 から始まります。したがって、p(2) = p(9) = \ldots = 3 です。
注意点として、位置 3 から始まる部分文字列 025 の各位の和は 7 ですが、各位の和が 7 である部分文字列 (位置 1 から始まる) がそれより前にあるので、p(7) = 1 です (3 ではありません)。
0 < k ≤ {10}^3 のとき、\sum p(k) = 4742 であることを確認できます。
0 < k ≤ 2 \times {10}^{15} のとき、\sum p(k) を求めなさい。
--hints--
infiniteStringTour() は 9922545104535660 を返す必要があります。
assert.strictEqual(infiniteStringTour(), 9922545104535660);
--seed--
--seed-contents--
function infiniteStringTour() {
return true;
}
infiniteStringTour();
--solutions--
// solution required