[AtCoder] CADDi 2018 for Beginners C – Product and GCD

Product and GCD

https://atcoder.jp/contests/caddi2018b/tasks/caddi2018_a

整数系の問題です。

考え方

題意

\( P \) は \( N \) 個の整数の積で表現したときに、その整数の最大公約数を答えます。

方針

どのような整数の組み合わせと \(P\) が最大公約数を最大化することを考えると、

\[ a_1 = a_2 = \cdots = a_N \]

であることが分かります。このとき、\( a = a_i \)とすると、

\[ a^N = P \]

なので、最大公約数は \( P^{\frac{1}{N}} \) となります。

しかし、このような \( P \) が与えられるとは限らないので、求める最大公約数の候補を \( t \) とし、

\[ 1 \leq t \leq P^{\frac{1}{N}} + 1\]

の範囲の中から、

\[ P \mod t^N = 0\]

を満たす最大の \( t \) を探せばよいです。上式を満たす \( t \) は、各整数について、\( a_i = t * b_i \) のように表現できることが保証されます。ここで、\( b_i \) は整数です。

また、\( N = 1\)のときは、\( P \) が答えとなります。

コード

シェアする

  • このエントリーをはてなブックマークに追加

フォローする