用 Python 编写程序，计算 n 的任何真因子为偶数完全平方数的概率

pythonserver side programmingprogramming更新于 2026/2/1 23:08:17

假设我们有一个数 n，我们必须计算 n 的任何真因子为偶数完全平方数的概率。

因此，如果输入为 n = 36，则输出为 1/8，因为 36 有八个真因子，分别是 {1,2,3,4,6,9,12,18}，其中只有一个数(4)是完全平方数且为偶数。

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

如果 n mod 4 不等于 0，则
- 返回 0
否则，
- nc := n, ptr := 2
- l := a new list
- 当 ptr <= nc 的平方根时，执行
  - a := 0
  - 当 nc mod ptr 与 0 相同时，执行
    - a := a + 1
    - nc := floor of (nc / ptr)
  - 如果 a > 0，则
    - 将 a 附加到列表 l
  - ptr := ptr + 1
- 如果 nc > 1，则将 1 附加到列表 l
- k := l[0]
- d := k + 1
- no := floor of (k / 2)
- 对于 l[从索引 1 到末尾] 中的每个 i，执行
  - d := d *(i + 1)
  - no := no * floor of (i / 2) + 1
- d := d - 1
- 如果 n 是完全平方数，则
  - no := no - 1
- g := d 和 no 的 gcd
- d := d / g 的 floor
- no := no / g 的 floor
- 如果 no 与 0 相同，则
  - 返回 0
- 否则，
  - return a fraction no/d

示例

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

from math import gcd

def solve(n):
   if n % 4 != 0:
      return 0
   else:
      nc = n
      ptr = 2
      l = []
      while ptr <= nc ** 0.5:
         a = 0
         while nc % ptr == 0:
            a += 1
            nc = nc / ptr
         if a > 0:
            l += [a]
         ptr += 1
      if nc > 1:
         l += [1]
      k = l[0]
      d = k + 1
      no = int(k / 2)
      for i in l[1:]:
         d = d * (i + 1)
         no *= int(i / 2) + 1
      d = d - 1
      if int(n ** 0.5) ** 2 == n:
         no -= 1
      g = gcd(d, no)
      d = d // g
      no = no // g
      if no == 0:
         return 0
      else:
         return str(no) + '/' + str(d)

n = 36
print(solve(n))