백준 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를 더했다

 

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