756 [AtCoder Beginner Contest 114 D]

https://beta.atcoder.jp/contests/abc114/tasks/abc114_d

解説

https://beta.atcoder.jp/contests/abc114/submissions/3708229

まずは、素因数分解のやり方である。（O(sqrt(N))のやり方）
ある数を素因数分解するには平方数までで割れれば割って数えていけばいい。
iで割るときにiが素数であるかを判定する必要があるようにも見えるが、実際にはiが合成数である場合に、
それを構成する素数で既に割られており、その合成数で割ることはできないので、問題ない。

map<int, int> enumpr(int n) {
    map<int, int> V;
    for (int i = 2; 1LL * i*i <= n; i++) while (n%i == 0) V[i]++, n /= i;
    if (n > 1) V[n]++;
    return V;
}

　
75=3*5*5であるので、約数が75になるためには、a^2*b^4*c^4となるように約数を取ればいい。
N!を素因数分解し、条件を満たす素数の組(a,b,c)を探すと答え。
b,cは普通に探すと、重複して数える可能性があるので、b＜cとして数えると良い。
他にも75, 3*25, 15*5の三通りあるので、同様に数え上げる。

int N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    
    map<int, int> sm;
    rep(i, 1, N + 1) {
        auto ep = enumpr(i);
        fore(p, ep) sm[p.first] += p.second;
    }
 
    int ans = 0;
 
    // 75
    rep(a, 2, N + 1) if (74 <= sm[a]) ans++;
 
    // 15*5
    rep(a, 2, N + 1) rep(b, 2, N + 1) if (a != b and 14 <= sm[a] and 4 <= sm[b]) ans++;
 
    // 3*25
    rep(a, 2, N + 1) rep(b, 2, N + 1) if (a != b and 24 <= sm[a] and 2 <= sm[b]) ans++;
 
 
    // 3*5*5
    rep(a, 2, N + 1) rep(b, 2, N + 1) rep(c, b + 1, N + 1) {
        if (a != b and a != c and 2 <= sm[a] and 4 <= sm[b] and 4 <= sm[c]) ans++;
    }   
    cout << ans << endl;
}