E - Divide Both Editorial by dokin
問題文
整数\(L,R\)が与えられるので、以下の条件を全て満たす整数組 \((x,y)\)の数を求めてください。
\(L \leq x,y \leq R\)
\(g=\gcd(x,y)\)に対し、以下が成立する。
- \(g \neq 1\) かつ \(\frac{g}{x} \neq 1\) かつ \(\frac{g}{y} \neq 1\)
制約
\(1 \leq L \leq R \leq 10^6\)
STEP0 事前準備
条件2の後半を扱いやすい形に変形します。
\(\frac{g}{x} \neq 1 \iff \gcd(x,y) \neq x \iff y\)は \(x\) の倍数ではない
\(\frac{g}{y} \neq 1 \iff \gcd(x,y) \neq y \iff x\)は \(y\) の倍数ではない
STEP1 数え上げの高速化
与えられた条件を満たす 整数組\((x,y)\)の個数 を数え上げる問題です。
愚直に数え上げると2乗オーダーかかり実行時間制限に間に合いません。何らかの高速化を考えましょう。
数え上げ問題の解法を2乗オーダーから1乗オーダーに落とす際、「1つの変数に着目し、その変数を固定した場合の問題を考えて高速化する」ことがしばしばあります。 今回は \(x\) と \(y\) の最大公約数 \(g= \gcd(x,y)\)に着目しましょう。
\(g\) を固定すると問題文は次のようにいいかえられます。
整数 \(L,R,g\) が与えられるので、以下の条件を満たす整数組 \((x,y)\) の数を求めてください。
1. \(L \leq x,y \leq R\)
2. \(\gcd(x,y) = g >1\)
3. \(x\) は \(y\) の倍数ではない。\(y\) は \(x\)の倍数ではない。
この問題の答えを \(F(g)\)とおきます。\(g\) としてあり得る範囲は \(2\) 以上 \(R\) 以下なので、 \(\sum _{g=2} ^{R} F(g)\) が答えです。
STEP 2 \(F(g)\)の導出
さて、 \(F(g)\) を高速に求めましょう。 まずは、比較的扱いやすそうな条件3に注目します。
条件2をみたし条件3をみたさないような \((x,y)\) について、次のいずれかが成り立っています。
- \(y = g\) かつ \(x\) は \(y\) の倍数
- \(x = g\) かつ \(y\) は \(x\) の倍数
\(L\) 以上 \(R\) 以下の範囲で、このような\((x,y)\)は簡単に数え上げることができます。
具体的には、条件1と条件2をみたすような\((x,y)\)の個数を \(F'(g)\) とおくと、
\(F(g) = F'(g)\) (\(1<g<L\)のとき)
\(F(g) = F'(g) - 2*\left\lfloor\frac{R}{g}\right\rfloor+1\) (\(L \leq g \leq R\)のとき)
です。
STEP3 \(F'(g)\)の導出(約数系包除)
\(F'(g)\) の求め方を考えます。 \(L\) 以上 \(R\) 以下の範囲で最大公約数が \(g\) となる整数組 \((x,y)\) の個数が \(F'(g)\)でした。
さて、最大公約数の定義を思い出しましょう。
整数 \(x,y\) に対し \((x,y)\) の最大公約数が \(g\) である
\(\iff\)
(i) \(g\) が \(x\) と \(y\) の公約数である
(ii) \(x\) と \(y\) は \(g\) よりも大きな公約数を持たない。
(i)を満たすものから(ii)を満たさないものを引くことにより、 \(F'(g)\) の値を求めましょう。
STEP3-1 \(g\) が \(x\) と \(y\) の公約数である
整数組 \((x,y)\)で、\(x\)と\(y\) がともに \(g\) の倍数であるものを数え上げればよいです。具体的には、 \(\left( \left\lfloor\frac{R}{g}\right\rfloor - \left\lfloor\frac{L-1}{g}\right\rfloor \right)^2\)個です。
STEP 3-2 \(x\)と\(y\)は\(g\)よりも大きな公約数を持たない。
整数 \(x,y\)に対し、
- \(g\) が \(x,y\) の公約数 \(\iff\) \(gcd(x,y)\) が \(g\) の倍数
が成り立ちます。
よって、STEP3-1の結果を用いると、
\[\left( \left\lfloor\frac{R}{g}\right\rfloor - \left\lfloor\frac{L-1}{g}\right\rfloor \right)^2 = \sum_{hはgの倍数} F'(h) = \sum_{j=1}^{\left\lfloor \frac{R}{g} \right\rfloor} F'(jg) \]
です。 移項すると、
\[F'(g) = \left( \left\lfloor\frac{R}{g}\right\rfloor - \left\lfloor\frac{L-1}{g}\right\rfloor \right)^2 - \sum_{j=2}^{\left\lfloor \frac{R}{g} \right\rfloor} F'(jg) \]
となります。
よって、\(g\) の値が大きい方から順番に \(F'(g)\) の値を求めることができます。 以上より、所望の整数組の個数を求めることができました。
各 \(F'(g)\)を求めるのにかかる計算量は\(O(R/g)\)です。よって、全体での計算量は\(O(R\log R)\)となり、実行時間制限に間に合います。
STEP3で行った議論はしばしば約数系包除と呼ばれる典型技法です。
posted:
last update: