この辺の (海外の ICPC 問題の) 記事書く人いなさそうなので書きます
問題概要
整数 が与えられる。 を満たす整数の組 であって が互いに素であるものの個数を求めよ。
- TL 1 sec
解法
※ 計算量を書くために、 としています。
お察しの通り を書いても落ちると思います。それよりも時間計算量が良いものを書く必要があります。
を、「 を満たす組 であって が互いに素であるものの個数」とします。元の問題で要求されていることとは微妙に異なりますが、この関数を組み合わせることで元の問題を表現することができます。具体的には を考えれば良いです (二次元累積和を実装したことがあるならば、それがイメージの助けになるかと思います)
では、この関数 はどのようにすれば高速に計算できるでしょうか?整数の組 の 以外で最小の公約数が であるとして、包除原理のように考えると以下のようになります。
- に含まれる素数が奇数個ならば、引かなければならないので引く
- に含まれる素数が偶数個ならば、引きすぎたぶんを足す
- ただし、 が平方数で割り切れる (つまりある素数 があって が で割り切れる) 場合は他の結果に包含されるので考慮しない
ここで「引く」「足す」「考慮しない」など、それぞれの場合の数に対して といった係数がかかることになりますが、この係数はまさにメビウス関数 (Mobius function) そのものです。この関数について詳しく知りたい方は メビウスの反転公式の証明と応用 | 高校数学の美しい物語 を見てください。メビウス関数はエラトステネスのふるいを動かす際に一緒に計算できるので、元の問題は で解けます。
ソースコード
const int MAXN = 10000010; int mu[MAXN + 5]; bool is_prime[MAXN + 5]; int main() { fill(is_prime + 2, is_prime + MAXN + 1, true); fill(mu, mu + MAXN + 1, 1); for(int i=2; i<=MAXN; i++) { if(!is_prime[i]) continue; mu[i] = -1; for(int k=i<<1; k<=MAXN; k+=i) { is_prime[k] = false; if((k/i) % i == 0) mu[k] = 0; else mu[k] = -mu[k/i]; } } int A, B, C, D; scanf("%d%d%d%d", &A, &B, &C, &D); auto calc = [&](int x, int y) { ll res = 0; for(int i=1; i<=min(x, y); i++) { res += 1LL * (x/i) * (y/i) * mu[i]; } return res; }; ll ans = calc(B, D) - calc(A-1, D) - calc(B, C-1) + calc(A-1, C-1); printf("%lld\n", ans); return 0; }