Cho pf = số lượng thừa số nguyên tố (có thể trùng). Cần tạo số n dương sao cho: (1) số thừa số nguyên tố ≤ pf, (2) số ước đẹp (nice divisors) lớn nhất. Ước đẹp = ước chia hết cho mọi thừa số nguyên tố của n. Trả về số ước đẹp max modulo 10⁹+7.
Ví dụ: pf = 5 → output = 6 (n=200=2³·5², ước đẹp: 10,20,40,50,100,200).
Giải thuật (Toán học: phân tích pf thành 3 và 2)
Số ước đẹp = tích (số mũ + 1) của các thừa số nguyên tố. Để tối ưu với tổng mũ cố định pf, nên chia pf thành nhiều 3 nhất có thể (và 2 nếu dư 1 hoặc 2).
- pf = 1 → 1
- pf = 3q + r: r=0 → 3^q; r=1 → 3^(q-1)·4; r=2 → 3^q·2
Code Python
def solve(pf):
if pf == 1:
return 1
m = 10**9 + 7
q, r = divmod(pf, 3)
if r == 0:
return pow(3, q, m)
elif r == 1:
return pow(3, q - 1, m) * 4 % m
else: # r == 2
return pow(3, q, m) * 2 % m
pf = 5
print(solve(pf)) # 6
Đầu vào / Đầu ra
Input: 5
Output: 6