[백준 11693번] n^m의 약수의 합 (Python3)

import sys
input = sys.stdin.readline
from math import sqrt
mod = 1000000007

def multiply(x,n):
  if n == 1:
    return x
  xn2 = multiply(x,n//2)
  if n%2:
    return xn2*xn2*x %mod
  else:
    return xn2*xn2 %mod

N,M = map(int,input().split())

N1 = N
prime = {}
for p in range(2,int(sqrt(N))+1):
  if N1%p:
    continue
  prime[p] = 0
  while N1%p == 0:
    N1 //= p
    prime[p] += 1
if N1 != 1:
  prime[N1] = 1

numer = 1
denom = 1
for p in prime:
  numer *= multiply(p,prime[p]*M+1)-1
  numer %= mod
  denom *= p-1
  denom %= mod
denom = multiply(denom,mod-2)

print(numer*denom %mod)

 

여러가지 수학지식을 섞어놓은 문제이다.

1. 등비수열의 합

2. 소인수 분해 (에라토스테네스의 체)

3. 분할정복을 이용한 거듭제곱

4. 모듈러 역원

 

을 이용해서 풀 수 있다.

 

 

오늘의 교훈) 모듈러 역원은 유용하다