[2022.05.18.] n^m의 약수의 합

문제 정보

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

난이도: Gold II

분류: [수학 → 정수론] [분할 정복 → 분할 정복을 이용한 거듭제곱]

 

문제 요약

$N^M$의 약수의 합을 구하면 됩니다. 정말 정직하죠?

 

풀이

$N$을 소인수분해한 결과가 아래와 같다고 합시다.

$N=p_1^{e_1}\times p_2^{e_2}\times \dots p_k^{e_k}$

그럼 $N^M$을 소인수분해한 결과는 자명히 아래와 같게 됩니다.

$N^M=p_1^{M{e}_1}\times p_2^{M{e}_2}\times \dots p_k^{M{e}_k}$

지금부터는 이 $M{e}_i$를 편의상 $e_i$라고 재정의하겠습니다.

 

그럼, 약수의 합은 어떻게 구할까요?

만약 위 소인수분해 결과에서 $k=1$이라면, 약수의 합은 $1+p_1+p_1^2+\cdots +p_1^{e_1}$이 됩니다.

$k=2$라면, $(1+p_1+p_1^2+\cdots +p_1^{e_1})(1+p_2+p_2^2+\cdots +p_2^{e_2})$가 됩니다.

이를 일반화할 수 있으며, $N^M$의 약수의 합은 $(1+p_1+p_1^2+\cdots +p_1^{e_1})(1+p_2+p_2^2+\cdots +p_2^{e_2})\cdots (1+p_k+p_k^2+\cdots +p_k^{e_k})$가 됩니다.

 

그럼 이 문제의 풀이는 $N^M$을 소인수분해해서 $(p_i,e_i)$ 쌍을 얻는 거랑

각 $(p,e)$ 쌍에 대해 $1+p+p^2+\cdots +p^e$를 구하는 게 됩니다.

 

앞부분은 $N$을 소인수분해한 뒤 각 지수에 $M$을 곱하는 방식으로 해결할 수 있으며,

뒷부분은 분할 정복을 이용한 거듭제곱과 이를 응용한 방식으로 해결할 수 있습니다.

뒷부분의 분할 정복을 요약하자면, $f(p,e)=1+p+p^2+\cdots +p^{e-1}$이라고 할 때

$f(p,e)=\{\begin{array}{ll}1& \text{if }e=1\\ f(p,e/2)+p^{e/2}+p^{e/2+1}f(p,e/2)& \text{if }e\text{ is odd}\\ f(p,e/2)+p^{e/2}f(p,e/2)& \text{if }e\text{ is even}\end{array}$가 됩니다.

const ll mod = 1e9 + 7;

ll fpw(ll a, ll b){
	ll res = 1, mul = a, bit = b;
	while (bit){
		if (bit & 1){ res = res*mul % mod; }
		mul = mul*mul % mod; bit >>= 1;
	}
	return res;
}
ll dnc(ll a, ll b){
	if (b == 1){ return 1; }
	ll bb = b >> 1;
	ll res = dnc(a, bb);
	if (b & 1){
		ll r1 = res, r2 = res * fpw(a, bb+1) % mod, r3 = fpw(a, bb);
		return (r1+r2+r3) % mod;
	}
	else{
		ll r1 = res, r2 = res * fpw(a, bb);
		return (r1+r2) % mod;
	}
}

vector<pl2> v;

void Main(){
	ll n, m; cin >> n >> m;
	if (m == 0){ cout << 1; return; }
	for (ll i = 2; i*i <= n; i++){
		if (n%i != 0){ continue; }
		ll cnt = 0;
		while (n%i == 0){ n /= i; cnt += m; }
		v.push_back({i, cnt});
	}
	if (n != 1){ v.push_back({n, m}); }
	ll ans = 1;
	for (pl2 pr : v){
		ll p = pr.fr, e = pr.sc;
		ll res = dnc(p, e+1);
		//cout << p << ' ' << e << " -> " << res << endl;
		ans *= res; ans %= mod;
	}
	cout << ans;
}