백준 - Σ (13172) [C++]

이 문제는 분할 정복을 이용해서 푸는 문제이다.

 

문제가 아주 어려운 얘기로 가득한데, 결론적으로 S1/N1 + S2/N2 + ... + SM/NM 을 구해야 하고, 여기서 곱셈 역원을 계산할 때 b^(x - 2) (mod X) 를 사용하라는 얘기이다. 

 

따라서 이 문제는 분할 정복을 사용하여 거듭제곱을 풀 수 있으면 된다.

값이 매우 크기 때문에 모듈러 연산을 곳곳에 배치해두었다.

 

중요한 점은 마지막 answer에도 모듈러 연산을 해줘야 정답이 나온다는 것이다.

#include <iostream>
#include <utility>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define MOD 1000000007

typedef long long LL;

LL calculate(LL a, LL x) {
	if (x == 0) {
		return 1;
	}

	if (x % 2 == 1) {
		return calculate(a, x - 1) % MOD * a % MOD;
	} else {
		LL result = calculate(a, x / 2) % MOD;
		return result % MOD * result % MOD;
	}
}

int M;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    
	LL answer = 0;
	cin >> M;
	for (int i = 0; i < M; i++) {
		LL N, S;
		cin >> N >> S;
		LL result = S * calculate(N, MOD - 2) % MOD;
		answer += result;
		answer %= MOD;
	}
	cout << answer << '\n';
	return 0;
}