[yukicoder] No. 811 約数の個数の最大化

2019年6月28日

問題

方針

約数の個数

\( i \) の約数の個数を \( d_i \) とします。\( i = nk \ (1\leq n \leq N \wedge 1 \leq k \leq N)\) を満たす \( i \) について、インクリメントさせます。

約数の個数のコード

素因数の個数

\( i \) の素因数の個数を \( g_i \) とすると、\( g_{ij} = g_{i} + g_{j} \) が成り立ちます。これを利用して求めます。

素因数の個数を求めるコード

共通の素因数の個数

\( a \) と \( b \) の共通の素因数の個数は、\( a \) と \( b \) の最大公約数の素因数の個数になります。

コード