CADDi 2018 C- Product and GCD

#include <bits/stdc++.h>

using namespace std;
using ll =long long;

#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cout << #x << " = " << (x) << endl;
bool coY() {cout <<"Yes"<<endl;}
bool coN(){cout <<"No"<<endl;}

const ll INF = 1LL << 60;

ll n,m;
string s;
//Write From this Line
vector<pair<ll,int>> factorize(ll n){
    vector<pair<ll,int>> res;
    for( ll i = 2; i*i <= n; ++i){
        if(n%i) continue ; 
        res.emplace_back(i,0);
        while(n%i == 0){
            n /= i ;
            res.back().second++;
        }
    }
    if ( n != 1) res.emplace_back(n,1);
    return res;
}

int main()
{
    cout << setprecision(10);
    ll p ;
    cin >> n >> p;

    vector<pair<ll,int>> fact = factorize(p);
    ll ans = 1; 
    for(auto x : fact){
        while(x.second >= n){
            ans *= x.first; 
            x.second -= n;
        }
    }
    cout << ans << endl;
}

解法

求める最大公約数をGとすると整数列 a1,a2,...,anは全てGの倍数になっているこのとき逆に、PはGⁿ の倍数になっている。 a1,a2,...anは全て因数に同じもの（Ｇ）を含んでいるということなので、 Pを素因数分解して、同じ素数がn個以上あるものを数えて掛け算してやればいい。

たとえばaが3個だってとき、p = 8なら p = 2 ^ 3 なので a1, a2 , a3 に2を1個ずつ割り当てればいい。

p = 64 = 2 ^ 6 ならa1 , a2 , a3 に2を2個ずつ割り当てることが出来る。