취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 13172번 문제인 Σ이다.
문제는 아래 링크를 확인하자.

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

문제의 형식에 따라 a/b를 저장하면 a * inv(b)이고, a/b와 c/d의 합은 (ad+bc) * inv(bd)와 같게 된다.

두 정수 x와 y에 대하여 xy%p = ((x%p)(y%p))%p와 같고, inv(x)%p = inv(x%p)%p 와 같다는 점을 확인하자.

한편 ad+bc와 bd가 서로소가 아니더라도 위의 식을 계산하면 공통인수가 서로 상쇄되므로, 분자와 분모만을 따로 관리하여 최종 분수의 분모와 분자를 얻어낼 수 있게 된다.

이를 이용하여 FLT(Fermat's Little Theorem)를 이용하여 inv(bd)를 계산하고 문제를 해결하자.

아래는 제출한 소스코드이다.

#define MOD 1000000007
#include <iostream>
using namespace std;
typedef long long ll;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	ll a = 0, b = 1;

	int M; cin >> M;
	while (M--) {
		ll c, d; cin >> d >> c;
		ll tmpa = (a * d + b * c) % MOD;
		ll tmpb = (b * d) % MOD;
		a = tmpa, b = tmpb;
	}

	int exponent = 1000000005;
	ll mult = b;
	ll tmp = 1;
	while (exponent > 0) {
		if (exponent & 1) tmp = (tmp * mult) % MOD;
		mult = (mult * mult) % MOD;
		exponent >>= 1;
	}

	cout << (a * tmp) % MOD;

}