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

สมมติว่าเราได้รับเลขจำนวนเต็มสองตัว m และ a ตอนนี้ n =p₁ ^{(a + 1)} *p₂ ^{(a + 2)} *...*p_m ^{(a + m)} โดยที่ p_i คือจำนวนเฉพาะที่ i และ i> 0 เราต้องหาค่าของ k โดยที่ k =ผลรวมของค่า f(x) ของ n โดยที่ค่า f(x) คือจำนวนค่าตัวหารของตัวหารแต่ละตัวของ n

ดังนั้น หากอินพุตเท่ากับ m =2, a =1 เอาต์พุตจะเป็น 60

• ดังนั้น n =2^2 x 3^3
• n =4 x 27
• n =108

ตัวหารของ 108 ได้แก่ 1, 2, 3, 4, 6, 9, 12, 18, 27, 36, 54, 108

f(x) ค่าของตัวหารแต่ละตัวคือ:f(1) + f(2) + f(3) + f(4) + f(6) + f(9) + f(12) + f(18) + ฉ(27) + ฉ(36) + ฉ(54) + ฉ(108)

=1 + 2 + 2 + 4 + 4 + 3 + 5 + 6 + 4 + 9 + 8 + 12

=60.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• MOD :=10^9 + 7
• กำหนดฟังก์ชัน summ() นี่จะใช้เวลา n
  • คืนค่าพื้นของ ((n * (n + 1)) / 2)
• กำหนดฟังก์ชัน division() นี่จะใช้เวลา a, b, mod
  • ถ้า mod b เหมือนกับ 0 แล้ว
    • คืนค่าพื้นของ a / b
  • a :=a + mod * ดิวิชั่น ((-a modulo b), (mod modulo b), b)
  • คืนค่าพื้นของ (a / b) modulo mod
• mat :=รายการใหม่ที่มีค่า 1
• ในขณะที่ขนาดของเสื่อ <=m + a ทำ
  • แทรก (องค์ประกอบสุดท้ายของ mat * summ(len(mat)+1)) mod MOD ที่ส่วนท้ายของ mat
• ผลตอบแทนส่วน(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))

อินพุต

2, 1

ผลลัพธ์

60