【ABC114】D - 756

atcoder.jp

解法

N!の約数を順に列挙していこうとすると、N次第ではN!がとてつもなく大きい数になってしまうため、現実的ではない。
そこで、約数を素因数を組み合わせた結果と考えることにする。
具体的には、1 ~ Nまでの数をそれぞれ素因数分解し、それぞれの素因数が何回登場したかを記録していき、最後に組み合わせ方を全探索する。

約数の個数を奇数にしようとすると、それぞれの素因数を選ばない or 偶数個使用する、の2択になるため、すべてを探索する必要はなかったりする。

実装

n重forループを使って書きたくなる全探索は、DFSによって表現することができる。

// ans: 答え, cnt: 約数の個数, iter: 次にどの素因数を探索するか, fac: N!を素因数分解した結果
void dfs(ll &ans, int cnt, int iter, vector<ll> &fac) {
    if (cnt == 75) {
        ans++;
        return;
    } else if (cnt > 75 || iter >= fac.size()) return;

    // 素因数を選ばない or 偶数個使用する場合だけ探索
    for (int i = 0; i <= fac[iter]; i += 2) {
        dfs(ans, cnt * (i + 1), iter+1, fac);
    }
}

void solve(long long N){
  // N!を素因数分解&集計
    map<ll, ll> fac;
    REP (i, N) {
        auto mp = prime_fac(i + 1);
        for (auto m : mp) fac[m.first] += m.second;
    }

  // 配列に移し替え(DFSをしやすくするため)
    vector<ll> vec;
    for (auto f : fac) vec.push_back(f.second);

    ll ans = 0;
    dfs(ans, 1, 0, vec);
    c(ans)
}