【ABC114】D - 756
解法
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) }