[백준 6930] Mod Inverse (C#, C++) - soo:bak

문제 링크

6930번 - Mod Inverse

설명

두 정수 x와 m이 주어질 때, x와 n을 곱한 값을 m으로 나눈 나머지가 1이 되는 n을 찾는 문제입니다. 그런 n이 없으면 해당 문구를 출력합니다.

접근법

범위가 작으므로 1부터 m-1까지 순회하며 조건을 만족하는 n을 찾습니다. 찾으면 출력하고, 없으면 문구를 출력합니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var x = int.Parse(Console.ReadLine()!);
    var m = int.Parse(Console.ReadLine()!);

    var found = false;
    for (var n = 1; n < m; n++) {
      if ((x * n) % m == 1) {
        Console.WriteLine(n);
        found = true;
        break;
      }
    }
    if (!found) Console.WriteLine("No such integer exists.");
  }
}

C++

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

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

  int x, m; cin >> x >> m;

  bool found = false;
  for (int n = 1; n < m; n++) {
    if ((x * n) % m == 1) {
      cout << n << "\n";
      found = true;
      break;
    }
  }
  if (!found) cout << "No such integer exists.\n";
  return 0;
}