問題概要 (ARC 034 C)
2 個の正整数 A,B が与えられる。 A! の約数であり、かつ B! の倍数でもあるような正整数の個数を 1,000,000,007 で割った余りを求めよ。
制約
- 1 <= B <= A <= 109
- 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; }