CADDi 2018 for Beginners C - Product and GCD

atcoder.jp

問題文だけ見ると、数学が苦手な人にはもはや無理な気しかしない。
なので、入力例と出力例を見ながら問題文を理解していった。

問題文意訳

「自然数がN個あって、それらを全てかけるとPになります。かけるとPになる自然数の組み合わせは色々ありますが、N個全体の最大公約数が一番大きくなるときの最大公約数はなんでしょう」です。（多分）

個人的な解法

入力例とか出力例を見てこんなことを考えた。

例1からの考え

この考え方をもとに、Pを割り切れる「答えのn乗」の、答えの最大値を1から順番に試していく。

nが132とかそれなりにあると、〇〇の132乗とかのようになって一瞬でPを越す。Pを越すと流石に割り切れなさそう。なので、1から順に試していって、gのn乗がPを越すまでがんばる。

n=1の時にこのやり方を使ってしまうと1~P回まで地道にやって時間が足りなくなってしまうので、n=1のときだけ入力例3のようにPをそのまま返すようにする。そうすればTLEが回避できる。

NもPも10の12乗まである。大きいかもと思ったらlong long intにしておく。
atcoder.jp

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

int main() {
  ll n, p;
  cin >> n >> p;

  if (n == 1) {
    cout << p << endl;
    return 0;
  }

  ll ans = 1;
  ll a = 1;
  while (pow(a, n) <= p) {
    ll kake = pow(a, n);
    if (p % kake == 0) ans = a;
    a++;
  }
  
  cout << ans << endl;
}

リンク先のやつを少しだけ改変してます。

これ今になって気づきましたがfor文でできますね。だれかfor文で実装してみてください。