Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 286 F問題 Guess The Number 2

AtCoder ABC286 ABC F問題 500 pts インタラクティブ

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

インタラクティブ問題

$1$ 以上 $10^9$ 以下の整数 $N$ が設定されているが, これは秘密である.

このとき, 次の手順を踏むことにより, $N$ を特定し, $N$ を出力せよ.

(Input) $1$ 以上 $110$ 以下の整数 $M$ 及び, $1$ 以上 $M$ 以下の整数の列 $A=(A_1, \dots, A_N)$ を出力する.
(Output) $A$ に対して, 次で定義される長さ $M$ の整数列 $B$ が与えられる. ただし, $B$ の第 $i$ 項は次で定義される $F$ に対して, $B_i=F^N(A_i)$ である.
(Input) $N$ を出力する.

制約

$1 \leq N \leq 10^9$

解法

以降では整数列 $A$ に対して, $F^N(A):=(F^N(A_1), \dots, F^N(A_N))$ と書くことにする.

$A=(2,3, \dots, M,1)$ とする. このとき, $B=(B_1, \dots, B_M)$ は $(B_1, B_1+1, \dots, M,1, \dots, B_1-1)$ の形をしている. また, $F^M(A)=A$ であり, $1 \leq k \lt M$ に対して, $F^k(A) \neq A$ である. よって, $F$ は $M$ 周期である. また, $A_1, F(A_1), \dots, F^{M-1}(A_1)$ は全て異なる.

よって, このように $A$ を設定することにより, $N$ を $M$ で割ったあまりを求めることができる.

今, $1$ つの $M$ について行ったが, これを $r$ 個の $M_1, \dots, M_r$ に対して独立に行い, 中国剰余定理を用いることによって, $N$ を $\operatorname{lcm}(M_1, \dots, M_r)$ で割った余りを求めることができる.

そして, 制約と合わせることにより, 次を満たす整数の列を $(M_1, \dots, M_r)$ を見つければ十分である.

$\operatorname{lcm}(M_1, \dots, M_r) \geq 10^9$
$M_1+\dots+M_r \leq 110$

これを満たす整数列の例としては以下がある (Hint: 対ごとに互いに素な整数の列における最小公倍数は総積に一致する).

$(M_1, M_2, M_3, M_4, M_5, M_6, M_7, M_8, M_9)=(4(=2^2), 9(=3^2), 5, 7, 11, 13, 17, 19, 23)$

実際,

$\operatorname{lcm}(M_1, M_2, M_3, M_4, M_5, M_6, M_7, M_8, M_9)=1338557220$
$M_1+M_2+M_3+M_4+M_5+M_6+M_7+M_8+M_9=108$

である.

中国剰余定理で $O(N \log \operatorname{lcm}(M_1, \dots, M_r))$ 時間かかり, これが (計算パートにおける) ボトルネックになる.