【典型90問】085 - Multiplication 085（★4）

問題リンク

解法

a,b,cのなかにKが持っていない素因数を持っている数が含まれることはないので、a,b,cは必ずKの約数だとわかる。
後は約数の中から条件を満たす組を全探索できれば良いが、最大5000個以上の約数を持つ可能性があるのでN³では間に合わない。
(高度合成数をネットなどで調べれば大体の最大値がわかる)
a,bが判明している時に、cはK/a/bになるので、これが条件を満たしているかどうかを判定することで、N²に改善することができる。(この問題を思い出した)

---

実装

std::setを使っているので、O(N² logN)だがギリギリ間に合う。

void solve(long long K) {
    vector<ll> div;

    // 約数列挙
    for (ll i = 1; i * i <= K; i++) {
        if (K % i == 0) {
            div.push_back(i);
            if (K/i != i) div.push_back(K/i);
        }
    }

    ll sz = div.size();
    set<vector<ll>> st;
    REP (i, sz) {
        REP (j, sz) {
            ll k = K/div[i]/div[j];

            if (div[i] * div[j] * k == K) {
                vector<ll> vec = {div[i], div[j], k};
                sort(all(vec));

                st.insert(vec);
            }
        }
    }

    c(st.size())
}