백준 13172번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
1초	512MB	골드 4

---

풀이

 문제가 이렇게 긴건 오랜만에 보는 것 같다. 결국은 모든 주사위를 한번씩 던졌을 때의 눈의 합의 평균을 나머지가 1000000007인 모듈러 역원을 통해 나타내라는 것이다. 모듈러 역원을 나타내는 방법은 여러가지가 있다. 문제에서는 소수 모듈러일때 가능한 페르마 소정리를 소개하고 있다.

 

 페르마 소정리를 간단하게 설명하면, 소수 p는 임의의 정수 a에 대해 a^p ≡ a (mod p)이며, a와 p가 서로소라면 a^(p-1) ≡ 1 (mod p) 을 만족하는 소수의 필요조건을 의미한다. 문제에서 말하듯, 여기서 한발 더 나아가면 a의 모듈러 역원은 a^(p-2) mod p를 통해 구할 수 있다는 것이다.

 

 물론 이는 정수론의 강력한 방법이지만, 다르게 풀어보고 싶었다. 이전에 중국인의 나머지 정리 알고리즘을 이용해 문제를 푼적이 있었는데(밀려있는 문제중 하나이다. 정리할 리스트에 있는 문제 ㅠㅠ), 중국인의 나머지 정리를 유도하기 위해서는 베주 항등식을 풀어내야 한다. 이를 풀어내기 위해서는 확장 유클리드 호제법(확장 유클리드 알고리즘이라고도 한다)을 이용한다. 모듈러 역원을 확장 유클리드 호제법으로 풀어내기 위해서는 베주 항등식의 꼴로 나타내야 한다. 우리가 모듈러 역원을 구하고자 하는 것은 입력에서는 n으로 표현하는 분모이다. n의 모듈러 역원을 x라고 해보자. 우리는 다음과 같은 합동식을 얻을 수 있다. 

이러한 합동식은 임의의 정수 k를 통해 다음과 같이 변형할 수 있다.

이때 n은 입력으로 주어지고, M은 문제에서 주어진 소수인 1000000007이다. n은 10억 이하이기 때문에, n과 M은 당연히 서로소이고, 베주 항등식이 성립할 조건은 등호 오른쪽의 정수가 GCD(n, M)이어야 한다. n과 M의 조건에 의해 해당 항등식을 만족하는 x와 y는 반드시 존재한다. 이제, 해당 항등식을 확장 유클리드 호제법으로 x를 찾아낸다면 문제는 해결된다. 이때, 확장 유클리드 호제법의 결과가 음수가 될 수 있기 때문에 모듈러에 유의한다.

코드 - 확장 유클리드 호제법

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MOD 1000000007LL

int m;
vector<pair<ll, ll>> dice;

void input() {
	cin >> m;
	dice.resize(m);
	for(auto& [n, s] : dice) cin >> n >> s;
}

tuple<ll, ll, ll> xGCD(ll a, ll b) {
	if (b == 0) {
		return {a, 1, 0};
	}
	auto[g, x, y] = xGCD(b, a%b);
	return {g, y, x-(a/b)*y};
}

void sol() {
	ll ans = 0LL;

	for(auto& [n, s] : dice) {
		auto [g, inv, y] = xGCD(n, MOD);
		ans += (s * ((inv + MOD) % MOD)) % MOD;
		ans %= MOD;
	}
	cout << ans;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	input();
	sol();
}

 

물론 페르마 소정리로도 문제를 간단하게 풀어내봤다.

코드 - 페르마 소정리

// input 함수와 main의 구성은 동일하다.

ll fast_square(ll a, ll b) {
	if (b == 0) return 1;
	if (b == 1) return a;

	ll tmp = fast_square(a, b/2) % MOD;

	if (b % 2) return (a * ((tmp * tmp) % MOD)) % MOD;
	else return (tmp * tmp) % MOD;
}

void sol() {
	ll ans = 0LL;

	for(auto& [n, s] : dice) {
		ll inv = fast_square(n, MOD - 2);
		ans += (s * inv) % MOD;
		ans %= MOD;
	}

	cout << ans;
}

위 : 페르마 소정리, 아래 : 확장 유클리드 호제법