파이썬에서 제수의 제수의 합을 구하는 프로그램

두 개의 정수 m과 a가 주어졌다고 가정합니다. 이제 n =p₁ ^{(a + 1)} *p₂ ^{(a + 2)} *...*p_m ^{(a + m)} , 여기서 p_i i 번째 소수이고 i> 0입니다. k 값을 찾아야 합니다. 여기서 k =n의 f(x) 값의 합입니다. 여기서 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) + f(27) + f(36) + f(54) + f(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() 함수를 정의합니다. 이것은, b, mod
  • mod b가 0과 같으면
    • 반환 하한값 / b
  • a :=a + mod * division((-a 모듈로 b), (모듈로 b), b)
  • (a / b) 모듈로 모드의 최소값 반환
• mat :=값 1을 포함하는 새 목록
• mat <=m + a의 크기 동안 do
  • 매트 끝에 (매트의 마지막 요소 * summ(len(mat)+1)) mod MOD 삽입
• 나누기 반환(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