結果

問題 No.3022 一元一次式 mod 1000000000
コンテスト
ユーザー Today03
提出日時 2025-02-15 01:55:59
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 934 bytes
コンパイル時間 3,578 ms
コンパイル使用メモリ 275,632 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2025-02-15 01:56:04
合計ジャッジ時間 4,884 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 8 WA * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

// 拡張ユークリッドの互除法
ll extGcd(ll a, ll b, ll &x, ll &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  ll d = extGcd(b, a % b, y, x);
  y -= (a / b) * x;
  return d;
}

int main() {
  int T;
  cin >> T;
  const ll MOD = 1'000'000'000;

  while (T--) {
    ll N, M;
    cin >> N >> M;

    ll g = gcd(N, MOD);
    if (M % g != 0) {
      cout << -1 << endl;
      continue;
    }

    // N / g, M / g, MOD / g にスケールダウン
    N /= g;
    M /= g;
    ll mod_g = MOD / g;

    // N * k ≡ -M (mod MOD) を解く
    // N * k ≡ -M (mod mod_g) に変形

    ll x, y;
    extGcd(N, mod_g, x, y); // x が N の逆元
    x = (x % mod_g + mod_g) % mod_g; // 正にする

    ll k = (-M % mod_g + mod_g) % mod_g;
    k = (k * x) % mod_g;

    // k を g 倍して元に戻す
    cout << k * g << endl;
  }

  return 0;
}
0