[백준 14579] 덧셈과 곱셈 (C#, C++) - soo:bak

문제 링크

14579번 - 덧셈과 곱셈

설명

구간의 삼각수 곱을 구하는 상황에서, 두 정수 a와 b (1 ≤ a < b ≤ 1,000)가 주어질 때, a부터 b까지 각 i에 대한 삼각수(1+2+…+i)를 모두 곱한 값을 14579로 나눈 나머지를 구하는 문제입니다.

예를 들어 a=2, b=4일 때, 삼각수는 각각 3, 6, 10이므로 3 × 6 × 10 = 180이고, 180 % 14579 = 180입니다.

접근법

누적합을 유지하며 각 i의 삼각수를 효율적으로 계산합니다.

1부터 a-1까지의 합을 먼저 계산한 후, a부터 b까지 순회하며 현재 i를 누적합에 더하면 i의 삼각수가 됩니다.

각 삼각수를 결과에 곱하되, 값이 커지므로 매 곱셈마다 14579로 나눈 나머지를 적용합니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    const int MOD = 14579;

    static void Main(string[] args) {
      var input = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
      var a = input[0];
      var b = input[1];

      var sum = 0;
      for (var i = 1; i < a; i++)
        sum += i;

      var result = 1;
      for (var i = a; i <= b; i++) {
        sum += i;
        result = (int)((result * (long)(sum % MOD)) % MOD);
      }

      Console.WriteLine(result);
    }
  }
}

C++

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

typedef long long ll;

const int MOD = 14579;

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

  int a, b; cin >> a >> b;
  
  int sum = 0;
  for (int i = 1; i < a; i++)
    sum += i;

  int result = 1;
  for (int i = a; i <= b; i++) {
    sum += i;
    result = (int)((result * 1LL * (sum % MOD)) % MOD);
  }
  
  cout << result << "\n";

  return 0;
}