約数

問題へのリンク

問題概要

$N$ が $K$ 未満になるまで以下の操作を繰り返す時、最終的に 1 になるような $K$ が何通り存在するか答えよ。

$N$ が $K$ で割り切れる：$N$ を ...

素因数分解を用いることで、約数の個数を簡単に求めることができます。

アルゴリズム

Nの約数の個数：

N を素因数分解する
それぞれの指数に1を足す
「2.」で得られたものを全てかけ合わせる

整数 N の約数とは「整数 N を割り切ることができる整数またはその集合」のことです。

単純なアルゴリズムでは約数の全列挙に $O(N)$ だけかかりますが、約数の性質を活かすと $O(\sqrt{N})$ で全列 ...

問題へのリンク

問題概要

N 個の整数列 $A_1, A_2, \cdots, A_N$ に、以下の操作をK回まで行う。これら全てはある数の倍数となるが、その数の最大値を求めよ。

操作：\(A_1, A_2, ...