백준 13172 c++

문제

너무 길어서 요약했다.
M개의 주사위가 있고, i번쨰 주사위가 $N_{i}$ 번째 주사위이며 모든 면에 적힌 숫자를 더한 값이 $S_{i}$일때 각 주사위에 대해 각 면이 나올 확률이 동일하다면, 모든 주사위를 한 번씩 던졌을 때 나온 숫자들의 합의 기댓값을 구하는 문제다.

이는 아래 방법을 따르는데,

$S_{1}/N_{1} + S_{2}/N_{2} + … + S_{M}/N_{M}$
를 계산할 때 따르는 통분 문제를 해결하기 위해 분수를 모듈러 상의 정수로 가지도록 한다.

기약 분수 $a/b = a * b^{-1}mod X$ 로 계산한다.
$b^{-1} * b = 1(modX)$

페르마의 소정리:

소수 모듈러에서
$b^{X-1} * b = 1(modX)$
가 성립하므로
$b^{X-2} = b^{-1}(modX)$

그러나 위와 같은 방식에서 서로 다른 분수를 모듈러 상 같은 정수로 저장하는 경우가 있고, 분모가 소인수X로 가지는 경우에 역원을 계산할 수 없어서 모둘러를 1,000,000,007과 같은 큰 소수로 한다.
이 방식을 최종으로 하여 문제를 푼다.

입력

첫 번째 줄에는 주사위의 수를 나타내는 정수 M(1 ≤ M ≤ 104)이 주어진다.

다음 M개의 줄은 각 주사위의 정보를 나타내며, 이 중 i(1 ≤ i ≤ M)번째 줄에는 Ni, Si(1 ≤ Ni, Si ≤ 109)가 공백으로 구분되어 주어진다.

출력

모든 주사위를 한 번씩 던졌을 때 나온 숫자들의 합의 기댓값을 출력한다. 정확한 판별을 위해, 답을 기약분수로 나타내었을 때 a/b가 된다면, (a × b-1) mod 1,000,000,007을 대신 출력하도록 한다. b-1은 b의 모듈러 곱셈에 대한 역원이다. 이 문제에서는 가능한 모든 입력에 대해 답이 존재한다.

---

풀이

#include <iostream>
#define MOD 1'000'000'007

using namespace std;
typedef long long ll;

ll power(ll a, ll b) {
  ll ret = 1;
  while(b) {
    if (b & 1)
      ret = ret * a % MOD;
    b /= 2;
    a = a * a % MOD;
  }
  return ret;
}

int main(void) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int M;
  cin >> M;
  ll ans = 0;

  for (int i = 0; i < M; i++) {
    int n, s;
    cin >> n >> s;
    ans += (s * power(n, MOD - 2)) % MOD;
    }
  cout << ans % MOD << '\n';
  return 0;
}