백준 11693번: n^m 의 약수의 합

https://www.acmicpc.net/problem/11693

11693번: n^m의 약수의 합

---

소인수분해를 $O\left ( \sqrt{N} \right )$ 에 구현할 수 있으면 충분한 문제입니다.

 

즉, trial division이라 부르는 방법을 쓰면 충분합니다.

 

일반적으로 다음이 알려져있습니다.

 

자연수 $N$ 이 소수 $p_{1},p_{2},\cdots,p_{m}$ 에 의해 다음과 같이 소인수분해 될 때,

$N=p_{1}^{\alpha_{1}}\times p_{2}^{\alpha_{2}}\times\cdots\times p_{m}^{\alpha_{m}}$

$\left ( 1 \right )$ $N$ 의 약수의 개수는 다음과 같다.

$\left ( \alpha_{1}+1 \right ) \times \left ( \alpha_{2}+1 \right ) \times \cdots \times \left ( \alpha_{m}+1 \right )$

$\left ( 2 \right )$ 또한 그 약수의 합은 다음과 같다.

$\left ( 1+p_{1}^{1}+p_{1}^{2}+\cdots+p_{1}^{\alpha_{1}} \right ) \times \left ( 1+p_{2}^{1}+p_{2}^{2}+\cdots+p_{2}^{\alpha_{2}} \right ) \times \cdots \times \left ( 1+p_{m}^{1}+p_{m}^{2}+\cdots+p_{m}^{\alpha_{m}} \right )$

 

각각을 등비수열의 합 공식을 이용해 계산하여 곱해주면 충분합니다. 페르마 소정리를 쓰면 됩니다.

 

$\left ( a+ar+ar^{2}+\cdots+ar^{n}=\frac{a\left ( r^{n+1}-1 \right )}{r-1} \right )$

 

단, 일반적인 trial division을 이용할 경우, $N$ 이 소수인 경우에 대한 예외처리가 필요합니다.

 

최종적인 코드는 다음과 같습니다.

#include <stdio.h>
#define mod 1000000007

long long power_modular (long long X, long long Y);

int main() {
	long long N, M;
	scanf("%lld %lld", &N, &M);
	
	long long temp, answer = 1;
	
	for (int i = 2; i * i <= N; i++) {
		if (N % i == 0) {
			long long count = 0;
			while(N % i == 0) {
				N /= i;
				count++;
			}
			temp = power_modular (i - 1, mod - 2);
			temp = (temp * ((power_modular(i, count * M + 1) - 1) % mod)) % mod;
			answer = (answer * temp) % mod;
		}
	}
	if (N > 1) {
		temp = power_modular(N, M + 1) - 1;
		if (temp < 0) {
			temp += mod;
		}
		answer = ((answer % mod) * temp) % mod;
		answer = (answer * power_modular(N - 1, mod - 2)) % mod;
	}
	
	printf("%lld", answer);
	
	return 0;
}

long long power_modular (long long X, long long Y) {
	X %= mod;
	long long result = 1;
	while (Y) {
		if (Y % 2) {
			result = (result * X) % mod;
		}
		X = (X * X) % mod;
		Y /= 2;
	}
	return result;
}

(C11, 1116KB, 0ms, 제출번호 27547521)

---

 

정수론적인 지식이 아주 필요한 편은 아닌 것 같은데, 티어가 좀 높게 배정된 것 같습니다.