백준 13172 Σ (c++) : 피너클

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

13172번: Σ

수학문제다.

일단 문제부터가 이해하기 어려워 하나씩 천천히 넘어가야한다.

우리는 모든 주사위를 한번씩 던졌을 때 나온 숫자들의 합의 기댓값을 구해야한다.

여기서 기댓값은

S1/N1 + S2/N2 + ... + SM/NM

이라고 나와있다.

근데 어떤 분수가 기약분수로 나타냈을 때 a/b면, 이 분수는  a × b-1 mod X (X는 소수)으로 대신 계산하란다.

우린 s/n을 s * n ^ -1 mod X (X는 소수)로 나타내야한다.

그런데 여기서 n ^ -1은 n ^ (X - 2) ≡ n ^ (-1) (mod X) 역시 성립한단다.

그럼 우리는 s/n을 s * n ^ (X - 2) mod X로 구해야한다. X는 1,000,000,007로 주어졌다.

cin >> m;
while (m-- > 0) {
	cin >> n >> s;
	ans += (s * solve(n, MOD - 2)) % MOD;
    ans %= MOD;
}

값을 입력받고 s 와 n을 위의 수식처럼 계산해주면 된다. 여기서 n ^ (1,000,000,007 - 2)를 계산할때

1,000,000,005번 계산하면 시간초과가 나온다. 그러니 분할정복으로 계산해준다.

long long solve(long long a, long long b) {
	long long p = 1;
	while (b > 0) {
		if (b % 2 == 1) {
			p = (p * a) % MOD;
		}
		a = (a * a) % MOD;
		b /= 2;
	}
	return p;
}

분할정복을 이용한 거듭제곱이다. b가 짝수면 서로 그대로 제곱하고 홀수면 이전에 저장한 수와 곱한다.

#include <iostream>

using namespace std;


const long long MOD = 1000000007;
long long ans = 0;
long long m, n, s;

long long solve(long long a, long long b) {
	long long p = 1;
	while (b > 0) {
		if (b % 2 == 1) {
			p = (p * a) % MOD;
		}
		a = (a * a) % MOD;
		b /= 2;
	}
	return p;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> m;
	while (m-- > 0) {
		cin >> n >> s;
		ans += (s * solve(n, MOD - 2)) % MOD;
        ans %= MOD;
	}
	cout << ans<< endl;
}

전체코드다.