AtCoder Beginner Contest 169, D : Div Game

問題文

　https://atcoder.jp/contests/abc169/tasks/abc169_d

問題概要

　正整数 $N$ が与えられる．$N$ に対し，以下の一連の操作を繰り返し行うことを考える．

1. 以下の条件を満たす整数 $z$ を選ぶ
   • ある素数 $p$ と正整数 $e$ で $p^e$ と書ける
   • $z \mid N$ である（$z$ は $N$ を割り切る）
   • 過去に $z$ として選んだことがない
2. $N \leftarrow \frac N z$

　最大で何回操作を行えるか？

制約

• $1 \leq N \leq 10^{ 12 }$

解法

　$N$ が $p_1^{ e_1 } \times p_2^{ e^2 } \times \dots \times p_M^{ e^M }$ と素因数分解できたとします．このとき，例えば $z$ として $p_i^{ k }$ と書ける数を選んだとすると，$z$ の素因数分での表現では置き換え操作によって $p_i$ の指数が $k$ だけ減って $p_i^{ e_i - k }$ で置き換わることになります．
　以上を踏まえて素因数分解での指数の列 $e_1, e_2, \dots, e_M $ に着目すると，各要素について，要素が $0$ でない限りにおいて相異なる正整数を選んで引く操作を行える，と言い換えることができます．このとき，過去に選んだことのない，できるだけ小さい正整数を選ぶのが明らかに得なので，選ぶべき数（素因数分解での表示における指数から引く数）は優先度が高いものから順に $1, 2, 3, \dots$ です．
　したがって，まず $N$ を素因数分解してから各素数ごとに出現回数を数えて指数を求め，上記の戦略で減じる数を選ぶ（$z$ を選ぶ）操作を繰り返せば，それが最適な戦略です．
　計算量としては，$N$ の素因数分解に一番時間がかかって，よくある実装では $O( \sqrt N )$ などになります．

コード

// 素因数分解 O( √N )
vector< long long > primeFactorization( long long N );

int main()
{
	IN( LL, N );

	const auto factors = primeFactorization( N );
	map< LL, int > counts;
	for_each( ALL( factors ), [&]( const int p ){ ++counts[p]; } );

	int res = 0;
	FOR( p, counts )
	{
		for ( int s = 1, i = 1; s <= p.snd; s += ++i )
		{
			++res;
		}
	}

	cout << res << endl;

	return 0;
}