Flatten [AtCoder Beginner Contest 152 E]

https://atcoder.jp/contests/abc152/tasks/abc152_e

前提知識

• LCM

解説

https://atcoder.jp/contests/abc152/submissions/9706493

条件を簡単にしよう。
条件をよくみると、A[i]B[i]=A[j]B[j]が全組み合わせある感じである。
ということは、全てのA[i]B[i]が同じ数になるという条件になることがわかる。

全てのA[i]B[i]が同じになるようにB[i]を決めて、かつ、B[i]の総和の最小値をとるという問題である。
ちょっとメタ読みな発想であるが、総和のmodの最小値というのは、modになっちゃってるので、
DPで比較みたいなことはできない。
なので、ある最適方針があるのではないかという方針で考える。

ある数をかけて全て同じ数にするというのは、公倍数と同じである。
そして、B[i]の総和を最小化したいということなので、最小公倍数を計算せよという問題となる。
なのでA[i]を素因数分解して、各素因数毎に個数の最大値を取って、全部合わせて最小公倍数を作ろう。
B[i]は最小公倍数/A[i]となるので、これをmod10⁹+7でやったら、でてくる。
これの総和が答え。

自分の解法ではmintでmod10⁹+7計算を全て隠蔽してある。

int N, A[10101];
map<int, int> primes[10101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) primes[i] = enumpr(A[i]);

    map<int, int> allPrimes;
    rep(i, 0, N) fore(p, primes[i]) chmax(allPrimes[p.first], p.second);
    mint lcm = 1;
    fore(p, allPrimes) lcm *= mint(p.first) ^ p.second;

    mint ans = 0;
    rep(i, 0, N) {
        mint b = lcm / mint(A[i]);
        ans += b;
    }
    cout << ans << endl;
}