用 Python 编写程序，查找 x 之间乘积为 x 且互质的对数

pythonserver side programmingprogramming更新于 2026/1/31 11:24:17

假设有一个函数 f(x)，它计算 (p, q) 对的数量，并且

1 < p <= q <= x
p 和 q 互质
p * q = x 因此如果我们有 n。

我们必须找到 1 到 n 范围内所有 i 的总和 f(x[i])。

因此，如果输入为 12，则输出将为 3，因为 x 值的范围为 1 到 12。

当 x = 6 时，有效对为 (2, 3)，因此 f(6) = 1
当 x = 10 时，有效对为 (2, 5)，因此 f(10) = 1
当 x = 12 时，有效对为 (3, 4)，因此 f(12) = 1

因此总共有 3对。

为了解决这个问题，我们将遵循以下步骤 −

count := 0
sqr := (n 的平方根) + 1 的整数部分
对于范围在 2 到 sqr - 1 的基数，执行
- 对于范围在 1 到基数最小值和 (n / 基数 - 基数 + 1) 的下限的 i，执行
  - 如果基数和 i) 的 gcd 不等于 1，则
    - 进行下一次迭代
  - count := count + floor of (n - i * base)/(base * base)
返回 count

示例

让我们看看下面的实现以便更好地理解 −

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))