【Python】積がxとなり互いに素であるペアの個数を効率的に求めるプログラム

問題の概要

関数 f(x) を考えます。f(x) は、次の条件をすべて満たすペア (p, q) の個数を返します。

• 1 < p ≤ q ≤ x
• p と q は互いに素(最大公約数が 1)
• p × q = x

ここで、正の整数 n が与えられたとき、x を 1 から n まで動かした場合の f(x) の総和を求めるのがこの問題の目的です。

入力例と出力例

たとえば入力が 12 の場合、出力は 3 になります。x が 1〜12 の範囲で条件を満たすのは次の 3 つだけだからです。

• x = 6 のとき:有効なペアは (2, 3) のみ → f(6) = 1
• x = 10 のとき:有効なペアは (2, 5) のみ → f(10) = 1
• x = 12 のとき:有効なペアは (3, 4) のみ → f(12) = 1

一方、たとえば x = 8(= 2 × 4)や x = 4(= 2 × 2)は、分解しても 2 つの数が互いに素にならないため、条件を満たすペアが存在しません。その結果、合計は 3 ペアとなります。

解法のアイデア

各 x について約数をすべて調べる素朴な方法でも解けますが、n が大きくなると計算量が膨れ上がります。そこで、次のような工夫を行います。

• ペア (p, q) のうち小さい方を base(= p)とし、大きい方の q を base で割った余り i に着目します。
• q は「base で割ると i 余れる数」なので、q = i + t × base(t ≥ 1)と表せます。
• gcd(base, i) = 1 であれば、q も base と必ず互いに素になります。したがって、x = base × q = base × i + t × base² という形の x をまとめて数えられます。
• 各 (base, i) の組に対して、x ≤ n を満たす t の個数は ⌊(n − i × base) / base²⌋ で一括して求まります。

この数え方により、ペアを 1 つずつ検証することなく、条件を満たすペアの総数を効率的に計算できます。

アルゴリズムの手順

1. count を 0 で初期化します。
2. sqr を「n の平方根の整数部分 + 1」とします。
3. base を 2 から sqr − 1 まで動かしながら、以下を繰り返します。
   • i を 1 以上 min(base, ⌊n / base⌋ − base + 1) 未満の範囲で動かします。
   • gcd(base, i) が 1 でない場合は、次の i へスキップします。
   • count に ⌊(n − i × base) / (base × base)⌋ を加算します。
4. count を返します。

Pythonでの実装例

理解を深めるために、以下の実装を見てみましょう。

from math import sqrt, gcd

def solve(n):
   count = 0
   sqr = int(sqrt(n)) + 1
   for base in range(2, sqr):
      for i in range(1, min(base, n // base - base + 1)):
         if gcd(base, i) != 1:
            continue
         count += (n - i * base) // (base * base)

   return count

n = 12
print(solve(n))

入力

12

出力

3

処理の流れ(n = 12 の場合)

• sqr = int(√12) + 1 = 3 + 1 = 4 となるため、base の候補は 2 と 3 です。
• base = 2 のとき:i = 1 のみが対象。gcd(2, 1) = 1 なので、count += (12 − 2) // 4 = 2(x = 6 と x = 10 に対応)。
• base = 3 のとき:i = 1 のみが対象。gcd(3, 1) = 1 なので、count += (12 − 3) // 9 = 1(x = 12 に対応)。
• 最終的に count = 3 が出力され、期待どおりの結果が得られます。