問題文

整数\(L,R\)が与えられるので、以下の条件を全て満たす整数組 \((x,y)\)の数を求めてください。

1. \(L \leq x,y \leq R\)

2. \(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で行った議論はしばしば約数系包除と呼ばれる典型技法です。