[백준 15818] 오버플로우와 모듈러 (C#, C++) - soo:bak

문제 링크

15818번 - 오버플로우와 모듈러

설명

n개의 정수를 곱한 값을 m으로 나눈 나머지를 구하는 문제입니다.

접근법

모든 수를 한 번에 곱하면 값이 너무 커져 오버플로우가 발생합니다.

모듈러 연산은 곱셈 중간에 적용해도 최종 결과가 같으므로, 숫자 하나를 곱할 때마다 나머지를 취해 값을 작게 유지합니다.

Code

C#

using System;

class Program {
  static void Main() {
    var nm = Array.ConvertAll(Console.ReadLine()!.Split(), long.Parse);
    var n = (int)nm[0];
    var mod = nm[1];
    var arr = Array.ConvertAll(Console.ReadLine()!.Split(), long.Parse);

    var ans = 1L;
    for (var i = 0; i < n; i++)
      ans = (ans * (arr[i] % mod)) % mod;
    Console.WriteLine(ans);
  }
}

C++

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

typedef long long ll;
typedef vector<ll> vll;

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

  int n;
  ll m;
  if (!(cin >> n >> m)) return 0;
  vll a(n);
  for (int i = 0; i < n; i++)
    cin >> a[i];

  ll ans = 1;
  for (int i = 0; i < n; i++)
    ans = (ans * (a[i] % m)) % m;
  cout << ans << "\n";

  return 0;
}