Hide

Problem E
コラッツの予想

/problems/collatzconjecture/file/statement/ja/img-0001.jpg

Picture by mscolly via Flickr.

1978年、アイザック・ニュートン卿は $\mathcal{P}$ は $\mathcal{NP}$の真部分集合であることを証明するかたわら、任意の自然数列 $a_1, \dots , a_ n$ に対するベータアルファパイゼータ関数 $f$ を次のように定義した。$1\leq i\leq j\leq n$ となる整数 $i, j$ に対して、$f(i, j) = \gcd (a_ i, a_{i+1}, \dots , a_{j-1}, a_ j)$.

約100年後、ローター・コラッツはこの関数を数列 $1, 1, 1, \dots , 1$に適用し、$f$ は常に $1$ になることを確認した。その結果、彼は任意の数列 $a_ i$ に対して $f$ は定値関数になると推測した。この推測は、現在ではコラッツの予想と称され、植物学における有名な未解決問題の1つとして挙げられる（厳格なコラッツの予想では、$f$ がどれだけ多くの値を取るとしても、実部は常に $\frac{1}{2}$ になる）。

あなたは駆け出しの文化人類学者として、この推測を裏付けることにした。与えられた数列 $a_ i$に対して、$f$ が取る値が何種類あるかを計算する。

入力

入力は2行で与えられる。

先頭行は $1 \leq n \leq 5 \cdot 10^5$となる整数で、数列の長さを表す。
次の行は数列 $a_1, a_2, \dots , a_ n$で、 $1 \leq a_ i \leq 10^{18}$ を満たす。

出力

単一の整数を含む単一行を出力する。これは、与えられた数列に対する関数がとる値の数を表す。

サンプル入力 1	サンプル出力 1
4 9 6 2 4	6

サンプル入力 2	サンプル出力 2
4 9 6 3 4	5

Problem Eコラッツの予想

入力

出力

Problem E
コラッツの予想