問題概要
2 個の正整数 A,B が与えられる。
- A! の約数である
- B! の倍数である
ような正整数の個数を 1,000,000,007 で割った余りを求めよ。
制約
解法
求める正整数は とおける。これが の約数であることから、
|
であることが言える。よって、 の約数の個数を丁寧に数え上げれば良い。
#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; }