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

13172번: Σ

cpp

#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 제곱을 구해줍니다.