はまやんはまやんはまやん

hamayanhamayan's blog

Product and GCD [CADDi 2018 C]

https://atcoder.jp/contests/caddi2018/tasks/caddi2018_a

解法

https://atcoder.jp/contests/caddi2018/submissions/3838129

a1×a2×...×aN=Pとなっているので、Pを素因数分解をしたときの素因数をa1~aNに分配していくことになる。
よって、Pをまずは素因数分解しよう。
素因数分解にはポラード・ロー素因数分解法があるが難しいので、sqrt(N)での素因数分解がおすすめ。
素因数分解が求められる場合は大体これで大丈夫。
(あとは、エラトステネスの篩をうまく使う方法もある)
 
ある素数pが、最大公約数に何個含めることができるかというのを考える。
それは、「a1~aNの中に含まれる素数pの最小個数」となる。
この最小個数を最大化するには、なるべく均等に分けていくのがいい。
ある素数pがc個ある場合は、aの1つの要素に含まれる少ない方の個数はfloor(c/N)となるので、
p^floor(c/N)の総積を取れば答え。

ll N, P;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> P;
    auto ep = enumpr(P);
 
    ll ans = 1;
    fore(p, ep) ans *= fastpow(p.first, p.second / N);
    cout << ans << endl;
}