백준 11693 - n^m의 약수의 합 [Python]

www.acmicpc.net/problem/11693

11693번: n^m의 약수의 합

등비수열의 합 이용

 

예를 들어 \(2^2 \times 3^3\) 으로 소인수분해가 되는 수가 있다고 할때, 이 수의 약수의 합은

\((1+2^1+2^2) \times (1+3^1+3^2+3^3)\) 이다.

 

어떤 수 \(N\)과 소수 \(p\)에 대해,

\(N = p^x\times C\)  (\(C\)는 자연수)  로 나타낼 수 있다고 해보자. 이때,

\(N^M = p^{xM} \times C^M\)  이므로,

소수 \(p\)에 대해

첫째항이 1이고, 공비가 \(p\)인 등비수열의

제 1항부터 제 \((xM+1)\)항까지의 합을 구한 후, 이를 정답에 곱해주는 것을 반복하면 된다.

 

\(\frac{p^{xM+1}-1}{p-1}\)를 구하면 된다.

 

(p-1)으로 나누는 부분은 모듈러 역수로 곱해줘야 한다.

MOD=1000000007
def getPow(a, x):
    ret=1
    while x:
        if x&1:
            ret=(ret*a)%MOD
        a=(a*a)%MOD
        x>>=1
    return ret
 
n,m=map(int,input().split())
ans=1
for i in range(2, int(n**0.5)+1):
    if n%i==0:
        c = 0
        while n%i==0:
            n//=i
            c+=1
        ans *= ( ( (getPow(i, c*m + 1)+MOD-1)%MOD ) * ( (getPow(i-1, MOD-2))%MOD ) )%MOD
        ans %= MOD
 
if n!=1:
    ans *= ( ( (getPow(n, m+1)+MOD-1)%MOD ) * ( (getPow(n-1, MOD-2))%MOD ) )%MOD
print(ans%MOD)

\(\sqrt{N}\)까지 돌리면서 \(N\)을 계속 나누어준다. 그래도 \(N\)이 1이 되지 않았다면, 현재의 \(N\)은 소수이므로 여기서 또 계산을 해줘야한다.

 

19번째 줄을 보면 \(i^{cM+1} - 1\)이 MOD의 배수가 될... 가능성은 모르겠어서 그냥 MOD를 더했다

 

내 머리에는 들어왔는데 설명하려니 힘들다