結果
問題 |
No.3022 一元一次式 mod 1000000000
|
ユーザー |
|
提出日時 | 2025-02-15 17:31:43 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 348 ms / 2,000 ms |
コード長 | 1,072 bytes |
コンパイル時間 | 3,213 ms |
コンパイル使用メモリ | 277,888 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2025-02-17 12:58:41 |
合計ジャッジ時間 | 4,825 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/math> using namespace std; using namespace atcoder; long long gcd_ext(long long a, long long b, long long &x, long long &y) { if (b == 0) { x = 1; y = 0; return a; } else { long long d = gcd_ext(b, a % b, y, x); y -= a / b * x; return d; } } long long inverse(long long a, long long P) { // aの逆元を求める long long x, y; gcd_ext(a, P, x, y); return (P + x % P) % P; } long long f(long long a, long long b, long long mod){ long long inva = inverse(a, mod); return (b*inva)%mod; } void solve(){ long long n, m; cin >> n >> m; long long mod = 1000000000; n %= mod; m = (mod - m%mod)%mod; long long g = __gcd(n, __gcd(m, mod)); if((n == 0 && m != 0) || __gcd(n/g, mod/g) > 1){ cout << -1 << endl; return; } if(n == 0 && m == 0){ cout << 1 << endl; return; } n /= g; m /= g; mod /= g; long long ans = f(n, m, mod); cout << (ans==0 ? 1000000000 : ans) << endl; return; } int main(){ int t; cin >> t; while(t--){ solve(); } }