[백준 20410] 추첨상 사수 대작전! (Easy) (C#, C++) - soo:bak

문제 링크

20410번 - 추첨상 사수 대작전! (Easy)

설명

선형합동법으로 난수를 생성할 때, 나머지 연산의 기준이 되는 소수와 초깃값, 그리고 처음 두 출력값이 주어지면 숨겨진 두 매개변수를 찾는 문제입니다.

접근법

선형합동법은 이전 값에 어떤 수를 곱하고 다른 수를 더한 뒤, 특정 수로 나눈 나머지를 다음 값으로 사용합니다. 첫 번째 출력은 초깃값에 이 연산을 적용한 결과이고, 두 번째 출력은 첫 번째 출력에 같은 연산을 적용한 결과입니다.

나머지 연산의 기준이 되는 수가 100 이하의 소수이므로, 찾아야 하는 두 매개변수도 각각 0 이상 그 수 미만입니다. 따라서 두 매개변수를 모두 완전 탐색하여 두 식을 동시에 만족하는 쌍을 찾으면 됩니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var parts = Console.ReadLine()!.Split();
    var m = int.Parse(parts[0]);
    var seed = int.Parse(parts[1]);
    var x1 = int.Parse(parts[2]);
    var x2 = int.Parse(parts[3]);

    for (var a = 0; a < m; a++) {
      for (var c = 0; c < m; c++) {
        if ((a * seed + c) % m != x1) continue;
        if ((a * x1 + c) % m != x2) continue;
        Console.WriteLine($"{a} {c}");
        return;
      }
    }
  }
}

C++

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

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

  int m, seed, x1, x2; cin >> m >> seed >> x1 >> x2;
  for (int a = 0; a < m; a++) {
    for (int c = 0; c < m; c++) {
      if ((a * seed + c) % m != x1) continue;
      if ((a * x1 + c) % m != x2) continue;
      cout << a << " " << c << "\n";

      return 0;
    }
  }

  return 0;
}