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

問題

方針

\( 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 \) が答えとなります。

コード

提出したコード

累乗の計算

  ll m = pow(P, (double) 1 / N) + 1;
  
  ll ans = 1;
  for (ll t = 2; t <= m; t++) {
    ll k = pow(t, N);
    if (P % k == 0) {
      ans = max(ans, t);
    }
  }

AtCoder,数学最大公約数

Posted by ヤマカサ