好き

問題概要

正の整数 $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;
}

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

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

CADDi 2018 C - Product and GCD (茶色, 300 点)

問題概要

考えたこと