[백준 13172] Σ (C#, C++) - soo:bak

문제 링크

13172번 - Σ

설명

M개의 주사위가 있고, 각 주사위의 면 수와 눈의 합이 주어집니다. 모든 주사위를 한 번씩 굴렸을 때 나오는 눈의 합의 기대값을 구하는 문제입니다. 답은 MOD = 1,000,000,007로 나눈 나머지로 출력해야 합니다.

접근법

먼저 각 주사위의 기대값은 눈의 합을 면 수로 나눈 값입니다. 전체 기대값은 각 주사위 기대값의 합이므로, 분수들의 합을 구해야 합니다.

다음으로 모듈러 연산에서 나눗셈은 직접 할 수 없으므로, 분모의 모듈러 역원을 곱합니다. MOD가 소수이므로 페르마 소정리에 의해 N의 역원은 N의 MOD-2 제곱입니다. 빠른 거듭제곱으로 O(log MOD)에 계산할 수 있습니다.

이후 각 주사위마다 S × N의 역원을 구해 더하고, 최종 결과를 MOD로 나눈 나머지를 출력합니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    const long MOD = 1_000_000_007;

    static long PowMod(long a, long e) {
      var res = 1L;
      while (e > 0) {
        if ((e & 1) == 1)
          res = res * a % MOD;
        a = a * a % MOD;
        e >>= 1;
      }
      return res;
    }

    static void Main(string[] args) {
      var m = int.Parse(Console.ReadLine()!);
      var ans = 0L;
      for (var i = 0; i < m; i++) {
        var parts = Array.ConvertAll(Console.ReadLine()!.Split(), long.Parse);
        var n = parts[0];
        var s = parts[1] % MOD;
        var inv = PowMod(n % MOD, MOD - 2);
        ans = (ans + s * inv) % MOD;
      }
      Console.WriteLine(ans);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll MOD = 1'000'000'007LL;

ll powmod(ll a, ll e) {
  ll res = 1;
  while (e > 0) {
    if (e & 1)
      res = res * a % MOD;
    a = a * a % MOD;
    e >>= 1;
  }
  return res;
}

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

  int m; cin >> m;
  ll ans = 0;
  for (int i = 0; i < m; i++) {
    ll n, s; cin >> n >> s;
    ll inv = powmod(n % MOD, MOD - 2);
    ans = (ans + (s % MOD) * inv) % MOD;
  }
  cout << ans % MOD << "\n";

  return 0;
}