Chương trình tìm tổng số ước của các ước trong Python

Giả sử chúng ta được cho trước hai số nguyên m và a. Bây giờ n =p ₁ ^{(a + 1)} * p ₂ ^{(a + 2)} * ... * p _m ^{(a + m)} , nơi p _i là số nguyên tố thứ i và i> 0. Ta phải tìm giá trị của k, trong đó k =tổng các giá trị f (x) của n. Ở đây giá trị f (x) là số giá trị ước của mỗi ước của n.

Vì vậy, nếu đầu vào là m =2, a =1, thì đầu ra sẽ là 60.

• Vì vậy, n =2 ^ 2 x 3 ^ 3
• n =4 x 27
• n =108

Các ước của 108 là:1, 2, 3, 4, 6, 9, 12, 18, 27, 36, 54, 108

Giá trị f (x) của mỗi ước là:f (1) + f (2) + f (3) + f (4) + f (6) + f (9) + f (12) + f (18) + f (27) + f (36) + f (54) + f (108)

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

=60.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• MOD:=10 ^ 9 + 7
• Xác định một hàm summ (). Điều này sẽ mất n
  • trả về giá trị sàn của ((n * (n + 1)) / 2)
• Xác định một phép chia hàm (). Điều này sẽ mất a, b, mod
  • nếu một mod b giống 0, thì
    • trả về giá trị sàn của a / b
  • a:=a + mod * chia ((- a modulo b), (mod modulo b), b)
  • trả về giá trị sàn của (a / b) modulo mod
• mat:=danh sách mới chứa giá trị 1
• while kích thước của mat <=m + a, do
  • insert (phần tử cuối cùng của mat * summ (len (mat) +1)) mod MOD vào cuối mat
• phân chia trả về (mat [m + a], mat [a], MOD)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

2, 1

Đầu ra

60