โปรแกรมหาผลรวมจำนวนตัวหารของตัวหารใน Python

กำหนดจำนวนเต็ม m และ a ให้ n = p₁^(a+1) × p₂^(a+2) × ... × p_m^(a+m) โดยที่ p_i คือจำนวนเฉพาะตัวที่ i ต้องการหาค่า k ซึ่งเป็นผลรวมของค่า f(x) ของทุกตัวหารของ n โดย f(x) คือจำนวนตัวหารของ x

ตัวอย่าง

อินพุต: m = 2, a = 1 → เอาต์พุต: 60

• n = 2² × 3³ = 4 × 27 = 108
• ตัวหารของ 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
• ผลรวม = 60

วิธีแก้ปัญหา

1. สร้างฟังก์ชัน summ(n) คืนค่า n(n+1)/2
2. สร้างฟังก์ชัน division(a, b, mod) สำหรับการหารแบบ modulo
3. สร้างอาร์เรย์ mat โดยใช้สูตรเวียนเกิด
4. คำนวณผลลัพธ์ด้วย division(mat[m+a], mat[a], MOD)

ตัวอย่างโค้ด

MOD = 10**9 + 7

def summ(n):
    return ((n) * (n + 1)) // 2

def division(a, b, 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))

อินพุต / เอาต์พุต

Input:  2, 1
Output: 60

หลักการ: ใช้คุณสมบัติของฟังก์ชันตัวหารและเลขคณิตแบบ modulo เพื่อคำนวณอย่างมีประสิทธิภาพโดยไม่ต้องหาตัวหารทั้งหมดโดยตรง