파이썬으로 n의 약수별 약수 개수(f(x)) 합계 구하는 프로그램

문제 개요

두 정수 m과 a가 주어졌다고 가정해 보겠습니다. 이때 n = p₁^(a+1) × p₂^(a+2) × … × p_m^(a+m)으로 정의되며, 여기서 p_i는 i번째 소수(i > 0)입니다. 우리가 구해야 할 값은 k이며, k는 n의 모든 약수 x에 대한 f(x) 값의 합입니다. 여기서 f(x)는 x가 가진 약수의 개수를 의미합니다.

예를 들어 입력이 m = 2, a = 1이라면 출력은 60이 됩니다.

n = 2² × 3³
n = 4 × 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

핵심 아이디어

n이 소수의 거듭제곱 곱 형태로 주어질 때, 각 약수 d의 약수 개수는 지수 조합에 따라 결정됩니다. 따라서 모든 약수에 대한 f(x)의 합은 소수별로 (1 + 2 + … + (지수 + 1))을 곱한 값으로 정리할 수 있습니다. 즉 k = ∏ summ(a + i + 1)이 되는데, 값이 매우 커질 수 있으므로 MOD = 10⁹ + 7 아래에서 모듈러 연산으로 계산하고, 나눗셈이 필요한 부분은 재귀적으로 구한 모듈러 역원을 활용해 처리합니다.

풀이 단계

이 문제는 다음 순서로 해결할 수 있습니다 −

MOD := 10⁹ + 7로 설정합니다.
함수 summ(n) : ((n × (n + 1)) / 2)의 내림 값을 반환합니다.
함수 division(a, b, mod) : 모듈러 환경에서의 나눗셈을 처리합니다.
- a mod b == 0이면 a // b를 그대로 반환합니다.
- 그렇지 않으면 a := a + mod × division((−a) mod b, mod mod b, b)로 재귀적으로 보정한 뒤 (a // b) mod mod를 반환합니다.
mat := 값 1을 담은 새 리스트로 초기화합니다.
mat의 길이가 m + a 이하인 동안, 리스트 끝에 (마지막 원소 × summ(len(mat) + 1)) mod MOD를 추가합니다.
최종적으로 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))

입력

2, 1