[백준 14928] 큰 수 (BIG) (C#, C++) - soo:bak

문제 링크

14928번 - 큰 수 (BIG)

설명

매우 큰 정수 N이 주어질 때, N을 20000303으로 나눈 나머지를 구하는 문제입니다.

입력되는 N은 최대 1천만 자리까지 가능하므로, 일반적인 정수 타입으로는 저장할 수 없습니다.

따라서 문자열로 입력을 받아 처리해야 합니다.

접근법

매우 큰 수를 직접 정수로 변환하지 않고, 문자열의 각 자릿수를 순회하며 모듈러 연산의 성질을 이용합니다.

예를 들어 123을 20000303으로 나눈 나머지를 구한다면, 1 → 12 → 123 순서로 한 자리씩 확장하며 매번 나머지를 계산합니다.

구체적으로 현재까지의 나머지를 r이라 하고, 다음 자릿수가 d일 때, 새로운 나머지는 (r × 10 + d) % 20000303이 됩니다.

이는 모듈러 연산의 분배 법칙 (a + b) % m = ((a % m) + (b % m)) % m과 (a × b) % m = ((a % m) × (b % m)) % m을 이용한 것입니다.

초기 나머지를 0으로 시작하여 문자열의 모든 자릿수를 순회하면 최종 나머지를 얻을 수 있습니다.

예를 들어 “1234”의 경우,

0 → (0 × 10 + 1) % 20000303 = 1

→ (1 × 10 + 2) % 20000303 = 12

→ (12 × 10 + 3) % 20000303 = 123

→ (123 × 10 + 4) % 20000303 = 1234 가 됩니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var n = Console.ReadLine()!.Trim();
      const int MOD = 20000303;
      var rem = 0L;

      foreach (var ch in n)
        rem = (rem * 10 + (ch - '0')) % MOD;

      Console.WriteLine(rem);
    }
  }
}

C++

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

typedef long long ll;

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

  string n; cin >> n;

  const int MOD = 20000303;
  ll rem = 0;

  for (char ch : n)
    rem = (rem * 10 + (ch - '0')) % MOD;

  cout << rem << "\n";

  return 0;
}