editorial は「75」という整数の特徴をフル活用している。
そして 75 という整数の特徴を活用しない DP による方法もあると説いている。

ここでは 75 という整数の特徴も活用せず、DP もしない (といっても DP への改良は容易) 愚直な全探索でも通った。

問題概要

正の整数 $N$ が与えられる。

$N!$ の約数のうち、約数の個数が 75 個であるようなものが何通りあるか数え上げよ。

制約

$1 \le N \le 100$

考えたこと

まず整数 $M$ の約数の個数について。

$M = p_{1}^{e_{1}} p_{2}^{e_{2}} \dots p_{K}^{e_{K}}$

と素因数分解できたとき、この整数 $M$ の約数の個数は

$(e_1 + 1)(e_2 + 1) \dots (e_K + 1)$ 個

となる。例えば 60 = 2² × 3 × 5 の約数の個数は (2+1)(1+1)(1+1) = 12 個となる。さて、 $N!$ の素因数分解は簡単。 $n = 2, 3, \dots, N$ をそれぞれ素因数分解して、各素数についての指数を合計すれば OK。

よって問題は、

$N! = 2^{A} 3^{B} 5^{C} \dots 97^{Z}$

みたいな素因数分解において、

$1 \le a \le A+1$
$1 \le b \le B+1$
...
$1 \le z \le Z+1$

なる組 $(a, b, \dots, z)$ であって、 $ab \dots z = 75$ となるものの個数を求める問題ということになる。

探索へ

$N = 100$ でも 543 通りしかないことがサンプル見てもわかる。あまり探索領域は広くなさそう。ということで再帰的な全探索で通すことにした。素因数分解の結果を

// sisuu[p] := 素因数分解における素数 p の指数
map<long long, int> sisuu;

によって表してあげて、

long long rec(map<long long, int>::iterator p, long long mul)

を、「sisuu のイテレータ p 以降について約数の個数を mul にするような場合の数」としてあげて再帰的に全探索した。

#include <iostream>
#include <vector>
#include <map>
using namespace std;

vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}

int N;
map<long long, int> sisuu;

long long rec(map<long long, int>::iterator p, long long mul) {
    if (p == sisuu.end()) {
        if (mul == 1) return 1;
        else return 0;
    }
    long long res = 0;
    for (int i = 0; i < p->second + 1; ++i) {
        if (mul % (i+1) != 0) continue;
        res += rec(++p, mul / (i+1));
        --p;
    }
    return res;
}

int main() {
    cin >> N;
    for (int i = 2; i <= N; ++i) {
        auto ps = prime_factorize(i);
        for (auto it : ps) sisuu[it.first] += it.second;
    }
    cout << rec(sisuu.begin(), 75) << endl;
}

DP に

この再帰関数を用いた全探索を、DP にするのは容易で、単にメモ化すれば OK。

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 114 D - 756 (水色, 400 点)

問題概要

制約

考えたこと

探索へ

DP に