けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

CADDi 2018 C - Product and GCD (300 点)

好き

問題へのリンク

問題概要

正の整数  N, P が与えられる。 a_1 × a_2 × \dots × a_N = P を満たすような  N 個の正の整数  a_1, a_2, \dots, a_N の組合せをすべて考えたとき、 a_1, a_2, \dots, a_N の最大公約数として考えられる最大値を求めよ。

考えたこと

 P素因数分解して、各素因子たちを  a_1, a_2, \dots, a_N に振り分けることを考える。

このとき、各素因数ごとに独立に考えてよいというのが 1 つの典型思考だと思われる。素因子  q について

  •  a_1 × a_2 × \dots × a_N = q^{k}

を満たすような振り分け方を考えると、その最大公約数が大きくなるには、 k 個の  q をなるべく均等に振り分けた方がいいことがわかる。均等にふりわけたとき、素因子  q の分についての最大公約数は

  •  q^{\lfloor \frac{k}{N} \rfloor}

となる。これを各素因子  q について掛け算していけばいい。

#include <iostream>
#include <vector>
using namespace std;

vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}

int main() {
    int N;
    long long P;
    cin >> N >> P;
    auto fac = prime_factorize(P);
    long long res = 1;
    for (auto p : fac) {
        for (int j = 0; j < p.second/N; ++j) res *= p.first;
    }
    cout << res << endl;
}