Chương trình xác suất ước số chính phương chẵn của n trong Python

Cho n, tìm xác suất ước số thực sự (proper divisor) của n là số chính phương chẵn.

Thuật toán

• Nếu n không chia hết 4 → trả về 0 (không có ước chính phương chẵn).
• Phân tích thừa số nguyên tố n, lấy số mũ.
• Số ước tổng = tích (mũ+1) - 1 (trừ chính n).
• Số ước chính phương chẵn: ước chứa 2^2k, các thừa số khác mũ chẵn.
• Rút gọn phân số bằng GCD.

Ví dụ

from math import gcd

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

print(solve(36))  # Output: 1/8

Giải thích

Ước thực sự của 36: {1,2,3,4,6,9,12,18} (8 ước). Chỉ 4 là chính phương chẵn → 1/8.