AtCoder ARC 034 C - 約数かつ倍数 (水色)

問題概要 (ARC 034 C)

2 個の正整数 A,B が与えられる。 A! の約数であり、かつ B! の倍数でもあるような正整数の個数を 1,000,000,007 で割った余りを求めよ。

制約

• 1 <= B <= A <= 10⁹
• A - B <= 100

解法

求める正整数は とおける。これが の約数であることから、

|

であることが言える。よって、 の約数の個数を丁寧に数え上げれば良い。

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

const int MOD = 1000000007;

int main() {
    long long A, B; cin >> A >> B;
    map<long long, long long> ma;
    for (long long n_ = B+1; n_ <= A; ++n_) {
        long long n = n_;
        for (long long p = 2; p*p <= n; ++p) {
            if (n % p != 0) continue;
            int num = 0;
            while (n % p == 0) ++num, n /= p;
            ma[p] += num;
        }
        if (n > 1) ma[n]++;
    }
    long long res = 1;
    for (auto it = ma.begin(); it != ma.end(); ++it) res = (res * (it->second+1)) % MOD;
    cout << res << endl;
}