AtCoder Regular Contest 034 C - 約数かつ倍数

問題

 正整数A, Bが与えられる。A!の約数であり、かつB!の倍数でもあるような整数の個数を求めよ。

解法

 求めるものは結局\frac{A!}{B!}の約数の個数である。これはB+1, \dots, Aまでの数字を素因数分解し、登場する素因数の数を数えていくことで求めることができる(約数の個数の公式)。各素因数分解にかかる計算量は数字nに対してO(\sqrt{n})であり、A - B \le 100という制約があるためこれでこの問題を解くことができた。

反省

 56分42秒(1WA)で久々に自力AC。まずこの手の問題を見たら初手としてやることは小さい数字での実験と決めているんだけど、この問題ではあまり有効ではなかったかもしれない。いろいろ見ているうちに、ようやくABの差分のところだけを考えればいいことに気が付く。しかし約数の個数を上手く求める方法を忘れていてその後もかなり手間取ってしまった。しばらくしてから素因数分解すれば求まるんだったなと思ってググって確証を得てから実装し、なんとかAC。一度素因数分解をするところをO(n)で実装してしまいTLEを出してしまった。そこまで難しい問題でもないと思うのでもっとすんなり解きたかった。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

constexpr ll MOD = (ll)1e9 + 7;

vector<pair<ll, ll>> getFactor(ll x) {
    vector<pair<ll, ll>> result;
    for (ll i = 2; i * i <= x; i++) {
        ll num = 0;
        while (x % i == 0) {
            x /= i;
            num++;
        }
        if (num) {
            result.push_back({ i, num });
        }
        if (x <= 1) {
            break;
        }
    }
    if (x > 1) {
        result.push_back({ x, 1 });
    }
    return result;
}

ll solve(ll a, ll b) {
    map<ll, ll> factor;
    for (ll i = b + 1; i <= a; i++) {
        auto f = getFactor(i);
        for (auto p : f) {
            factor[p.first] += p.second;
        }
    }

    ll ans = 1;
    for (auto p : factor) {
        ans *= p.second + 1;
        ans %= MOD;
    }
    return ans;
}

int main() {
    ll A, B;
    cin >> A >> B;
    cout << solve(A, B) << endl;
}