問題
正整数が与えられる。の約数であり、かつの倍数でもあるような整数の個数を求めよ。
解法
求めるものは結局の約数の個数である。これはまでの数字を素因数分解し、登場する素因数の数を数えていくことで求めることができる(約数の個数の公式)。各素因数分解にかかる計算量は数字に対してであり、という制約があるためこれでこの問題を解くことができた。
反省
56分42秒(1WA)で久々に自力AC。まずこの手の問題を見たら初手としてやることは小さい数字での実験と決めているんだけど、この問題ではあまり有効ではなかったかもしれない。いろいろ見ているうちに、ようやくとの差分のところだけを考えればいいことに気が付く。しかし約数の個数を上手く求める方法を忘れていてその後もかなり手間取ってしまった。しばらくしてから素因数分解すれば求まるんだったなと思ってググって確証を得てから実装し、なんとかAC。一度素因数分解をするところをで実装してしまい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; }