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

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

AtCoder ABC 114 D - 756 (400 点)

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 = 22 × 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。