AtCoder Beginner Contest 114 ABC114 D - 756

問題へのリンク

問題概要

個の約数なので、その性質自体を活かした解法もあるが、今回はあえて一般的な問題として捉え、DPをしてみる。

dp[i][j]: i個目までの素因数で約数の個数がj個

とする。

dp[0][1] = 1として（の約数は個と考える）

個の約数を持つ数に、をかけると、個の約数を持つ数になる。

よって、 dp[i+1][j * (k + 1)] += dp[i][j]として、更新する。

これを ~ まで遷移させれば良い。

提出

ll dp[100][100];

int main() {

    int N;
    cin >> N;
    map<int, int> fac;
    rep1(y,N+1){
        int x = y;
        for(int i = 2; i * i <= x; i++){
            while (x%i == 0) {
                x /= i;
                fac[i]++;
            }
            if (x == 1) break;
        }
        if (x != 1) fac[x]++;
    }
    vector<int> fav;
    for(auto p:fac)fav.push_back(p.second);
    int M = fav.size();
    dp[0][1] = 1;
    rep(i,M){
        rep(j,100){
            rep(cnt, fav[i]+1){
                dp[i+1][min(100, j * (cnt + 1))] += dp[i][j];
            }
        }
    }
    cout << dp[M][75] << endl;
}