2020年2月26日水曜日

CodeChef UWCOI 2020 - Blocks

CodeChef UWCOI 2020 - Blocks

整数xxを質問して答えNxN-xが帰ってくること(つまり、末尾まで一致していること)と、問題の列が長さxxのprefixの繰り返しになっていることは同値である。質問するxxNNの約数だけでよくて、 10610^6以下の自然数の約数の数は高々240240個なので、すべて調べれば部分点が取れる。

NNを素因数分解してN=p1e1p2e2...pkekN = p_1^{e_1}p_2^{e_2}...p_k^{e_k}とする。N/pieiN/p_i^{e_i}を質問して末尾まで一致している\Leftrightarrow素因数pip_iは必要ない、が成り立つので、これで必要な素因数を割り出したあと、それぞれの指数に関して二分探索すればよい。高々9回で可能というのは全列挙で示すしかなさそう?