AtCoder Beginner Contest 243 G問題 Sqrt

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

次を満たす長さ $10^{100}$ の列 $A$ の個数を求めよ.

$A_1=X$
$i=1,2, \dots, 10^{100}$ に対して, $1 \leq A_i$
$i=1,2, \dots, 10^{100}-1$ に対して, $A_{i+1} \leq \sqrt{A_i}$ である.

$T$ 個のテストケース

制約

$1 \leq T \leq 20$
$1 \leq X \leq 9 \times 10^{18}$

解法 1

まず, $1 \leq A_i \leq \sqrt[2^{i-1}]{X}$ である. $X \leq 9 \times 10^{18}$ なので, $i=7$ とした $1 \leq A_i \leq \sqrt[64]{X}$ は $A_i=1$ を意味する. $7 \lt 10^{100}$ より, 「長さ $10^{100}$ 」は「長さ (可算) 無限」に置き換えても良い.

この置き換えにより, $X$ があたえられた場合の答え $S_X$ を第 $2$ 項目で場合分けすることにより,

$\displaystyle S_1=1, \quad S_X=\sum_{Y=1}^{\left \lfloor \sqrt{X} \right \rfloor} S_Y$

となることがわかる. これを累積和を用いて実装すると, 時間計算量 $O(\sqrt{X})$ となってしまい, 間に合わない.

解法 2

解法 1 では $A_2$ に着目していたが, $A_3$ について着目する. $A_1, A_3$ が固定されているとき, $A_2$ として可能なのは

$A_3^2 \leq A_2 \leq \left \lfloor \sqrt{X} \right \rfloor$

である. そして, $A$ は無限列としているので, $A_1=X, A_3=\alpha$ であるような整数列の数は $\max(0, \left \lfloor \sqrt{X} \right \rfloor-\alpha^2+1) S_\alpha$ である.

また, $\alpha$ について, $\alpha^4 \leq X$ . つまり, $\alpha \leq \sqrt[4]{X}$ でなくてはならない. 以上から,

$\displaystyle S_X=\sum_{\alpha=1}^{\sqrt[4]{X}} \left(\left \lfloor \sqrt{X} \right \rfloor-\alpha^2+1 \right) S_\alpha$

となり, 時間計算量 $O(\sqrt[4]{X})$ で求めることができる.

解法 3

今回, $X \leq 9 \times 10^{18}$ なので, $\sqrt[4]{X} \leq 54772=:M$ であるから, 解法1を用いて $S_1, \dots, S_T$ を求め, 各問について, $X \leq M$ ならば前計算の結果をそのまま答え, $X \gt M$ ならば, 解法2を用いて $S_X$ を求める方針を取れば, 1テストファイルあたりの時間計算量 $O(T \sqrt[4]{X})$ で求めることができる.