[백준 C++] 13172 Σ - 정수론

13172번: Σ

#include <iostream>
#include <numeric>
using namespace std;

typedef long long ll;
const ll Mod = 1000000007;

ll Pow(ll X, ll Y)
{
	if (Y == 1)
	{
		return X;
	}

	if (Y % 2 == 1)
	{
		return X * Pow(X, Y - 1) % Mod;
	}

	ll Z = Pow(X, Y / 2);
	return Z * Z % Mod;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	int M;
	cin >> M;

	ll Sum = 0;
	for (int i = 0; i < M; ++i)
	{
		int A, B;
		cin >> B >> A;

		ll GCD = gcd(A, B);
		B /= GCD;
		A /= GCD;

		Sum += A * Pow(B, Mod - 2) % Mod;
		Sum %= Mod;
	}

	cout << Sum;
}

---

 

문제 설명이 길지만 핵심 내용은 다음과 같습니다.

 

1. 입력 받은 값을 기약 분수로 표현

2. 수식 b^(X - 2) ≡ b-1 (mod X) 에서 큰 수  b^(X - 2) 구하기

 

1번의 경우 numeric stl에 포함된 gcd(최대공약수) 구하는 함수를 이용해서 A와 B를 기약 분수 꼴로 표현 합니다.

2번의 경우 재귀 함수를 이용해서 b의 Mod - 2 제곱을 구해줍니다.