Cho hai số nguyên m và a. Xét n = p₁^(a+1) × p₂^(a+2) × ... × pₘ^(a+m), trong đó p_i là số nguyên tố thứ i. Tìm k = Σ f(x) với x chạy qua tất cả ước của n, trong đó f(x) = số ước của x.
Ví dụ
Input: m=2, a=1 → Output: 60
n = 2² × 3³ = 4 × 27 = 108
Ước của 108: 1,2,3,4,6,9,12,18,27,36,54,108
f(x): 1,2,2,4,4,3,5,6,4,9,8,12 → Tổng = 60
Công thức toán học
Với n = ∏ p_i^{e_i}, tổng số ước của các ước = ∏ [ (e_i+1)(e_i+2)/2 ]
Ở đây e_i = a+i. Kết quả = ∏_{i=1..m} (a+i+1)(a+i+2)/2
Mã nguồn (tối ưu modulo)
MOD = 10**9 + 7
def summ(n):
return (n * (n + 1)) // 2
def division(a, b, mod):
"""Chia modulo: tính a/b mod mod"""
if a % b == 0:
return a // b
a += mod * division((-a) % b, mod % b, b)
return (a // b) % mod
def solve(m, a):
mat = [1]
while len(mat) <= m + a:
mat.append((mat[-1] * summ(len(mat) + 1)) % MOD)
return division(mat[m + a], mat[a], MOD)
print(solve(2, 1)) # Output: 60Giải thích thuật toán
Mảng mat lưu tích lũy: mat[k] = ∏_{i=1..k} summ(i) = ∏_{i=1..k} i(i+1)/2 = (k+1)! * k! / 2^k
Kết quả cần = mat[m+a] / mat[a] = ∏_{i=a+1..m+a} i(i+1)/2 = ∏_{j=1..m} (a+j)(a+j+1)/2. Đúng công thức.
Hàm division thực hiện chia modulo bằng đệ quy dựa trên định lý Euler/Fermat (mod là số nguyên tố).