[BOJ] 13172 Σ

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

13172번: Σ

알고리즘: 분할정복(제곱)

---

 

$\frac{S_1}{N_1}+\frac{S_2}{N_2}에서,\\$ $\frac{S_1}{N_1}: a_1 \times b_1^{-1}\ \left(mod\ X\right)\\$ $\frac{S_2}{N_2}: a_2 \times b_2^{-1}\ \left(mod\ X\right)\\$ $\frac{S_1}{N_1}+\frac{S_2}{N_2} : a_1 \times b_1^{-1}\ \left(mod\ X\right) + a_2 \times b_2^{-1}\ \left(mod\ X\right)$ 이 성립한다.

 

분할정복을 이용하여 X-2제곱(=10^9 + 5)을 구해주고 각각을 다 더해주면 AC.

 

 

	#include <iostream>
	#include <algorithm>
	using namespace std;
	typedef long long ll;
	int M, p;
	ll N, S, ans, b;
	const int X = 1e9 + 7;
	int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> M;
	while(M--){
	cin >> N >> S;
	p = X - 2;
	b = 1LL;
	while (p){
	if (p & 1) b = (b * N) % X;
	N = (N * N) % X;
	p >>= 1;
	}
	ans = (ans + (S * b) % X) % X;
	}
	cout << ans;
	return 0;
	}

view raw BOJ_13172.cpp hosted with ❤ by GitHub