[C++] 백준 13172번: ∑

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

13172번: Σ

문제 이해를 실패했다. 다른 사람의 블로그 글을 보고도 이해를 하지 못 했다. 다만, 여러 번 쉬는 시간을 가지고 시간이 좀 지난 후 다시 보니 무엇을 해야 하는지 이해가 됐다. 내가 이해한 것은 다음과 같다.

1. 주사위의 면의 개수와 각 면에 적힌 수들의 합이 N, S로 주어진다.

2. 각 주사위에 대한 기대값은 분수로 나타낼 수 있다.

3. 모든 주사위에 대한 기대값은 각 주사위에 대한 기대값의 합으로 나타낼 수 있다.

4. 모든 주사위에 대한 기대값을 구하려면 통분을 하는 등 계산이 복잡하다.

5. 계산의 편의성을 위해 각 주사위에 대한 기대값을 모듈로로 나타내도록 한다.

6. 먼저 각 주사위에 대한 기대값을 기약분수로 나타낸다.

  - 이 때, 유클리드 호제법을 활용한다.

7. 그렇게 구한 기약분수가 \(\frac{a}{b}\)라고 하자.

8. 페르마의 소정리에 의해 \(\frac{a}{b}={a}\times{b^{-1}}\equiv{a}\times{b^{X-2}}\text{ mod X}\)이다.

  - 이유는 알려고 하지 말자.

9. 우리가 구해야 하는 답은 \((\sum_{}^{M}{{a_{i}}\times{b_{i}^{X-2}}\text{ mod X}})\text{ mod X}\)이다.

그 코드가 아래와 같은데, 이유는 모르겠지만 4%에서 WA를 받는다.

#include <bits/stdc++.h>

using namespace std;

#define TC(T) int T; cin >> T; while(T--)
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define ERR 1e-13
#define EL "\n"
#define VI vector<int>
#define VVI vector<VI>
#define VVVI vector<VVI>
#define VP vector<pair<int, int>>
#define VVP vector<VP>

/* declare variables here */
#define X 1000000007
#define ULL unsigned long long
int M;
VP NS;

/* define debug functions here */


/* define functions here */
ULL power(int base, int exp) {
	if (exp == 1)
		return base;
	ULL ret = power(base, exp / 2);
	if (exp % 2)
		return (ret * ret * base) % X;
	return (ret * ret) % X;
}

ULL inverseOf(int n) {
	return power(n, X - 2);
}

int gcdBetween(int a, int b) {
	if (b == 0)
		return a;
	return gcdBetween(b, a % b);
}

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	/* Write input codes here  */
	cin >> M;
	NS = VP(M);
	FOR(i, M)
		cin >> NS[i].first >> NS[i].second;

	/* Write solution codes here */
	ULL ans = 0;
	for (const auto& ns : NS) {
		const auto& [n, s] = ns;
		int gcd = gcdBetween(n > s ? n : s, n < s ? n : s);
		int a = s / gcd;
		int b = n / gcd;
		ans = (ans + (ULL)a * inverseOf(b)) % X;
	}
	cout << ans << EL;

	return 0;
}

오버플로우 문제도 아니고, 식도 제대로 잘 썼는데도 틀린다.

진짜 뭐가 문제인지 모르겠다.

.

.

.

문제를 찾았다. 오버플로우 문제가 아니지 않았다.

문제를 찾을 땐 뭐든지 확신을 가지면 안 된다.

power 함수에서 exp가 홀수일 때 ret * ret * base를 해줬는데, 여기서 unsigned long long 범위를 넘어간다.

이를 ((ret * ret) % X) * base로 바꾸어 AC를 받았다.

정말 오래 걸렸다.

#include <bits/stdc++.h>

using namespace std;

#define TC(T) int T; cin >> T; while(T--)
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define ERR 1e-13
#define EL "\n"
#define VI vector<int>
#define VVI vector<VI>
#define VVVI vector<VVI>
#define VP vector<pair<int, int>>
#define VVP vector<VP>

/* declare variables here */
#define X 1000000007
int M;
VP NS;

/* define debug functions here */


/* define functions here */
unsigned long long power(int base, int exp) {
	if (exp == 1)
		return base;
	unsigned long long ret = power(base, exp / 2);
	if (exp % 2)
		return (((ret * ret) % X) * base) % X;
	return (ret * ret) % X;
}

unsigned long long inverseOf(int n) {
	return power(n, X - 2);
}

int gcdBetween(int a, int b) {
	if (b == 0)
		return a;
	return gcdBetween(b, a % b);
}

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	/* Write input codes here  */
	cin >> M;
	NS = VP(M);
	FOR(i, M)
		cin >> NS[i].first >> NS[i].second;

	/* Write solution codes here */
	unsigned long long ans = 0;
	for (const auto& ns : NS) {
		auto [n, s] = ns;
		int gcd = gcdBetween(n > s ? n : s, n < s ? n : s);
		n /= gcd;
		s /= gcd;
		ans = (ans + (unsigned long long)s * inverseOf(n)) % X;
	}
	cout << ans << EL;

	return 0;
}