結果
問題 | No.2117 中国剰余定理入門 |
ユーザー | wanui |
提出日時 | 2022-11-04 23:10:43 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 2,419 bytes |
コンパイル時間 | 1,994 ms |
コンパイル使用メモリ | 201,480 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-18 21:04:03 |
合計ジャッジ時間 | 2,689 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 1 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 1 ms
5,376 KB |
testcase_17 | AC | 1 ms
5,376 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> // clang-format off using namespace std; using ll=long long; using ull=unsigned long long; using pll=pair<ll,ll>; const ll INF=4e18; void print0(){}; template<typename H,typename... T> void print0(H h,T... t){cout<<h;print0(t...);} void print(){print0("\n");}; template<typename H,typename... T>void print(H h,T... t){print0(h);if(sizeof...(T)>0)print0(" ");print(t...);} void perr0(){}; template<typename H,typename... T> void perr0(H h,T... t){cerr<<h;perr0(t...);} void perr(){perr0("\n");}; template<typename H,typename... T>void perr(H h,T... t){perr0(h);if(sizeof...(T)>0)perr0(" ");perr(t...);} void ioinit() { cout<<fixed<<setprecision(15); cerr<<fixed<<setprecision(6); ios_base::sync_with_stdio(0); cin.tie(0); } #define debug1(a) { cerr<<#a<<":"<<a<<endl; } #define debug2(a,b) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<endl; } #define debug3(a,b,c) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<endl; } #define debug4(a,b,c,d) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<" "<<#d<<":"<<d<<endl; } // clang-format on 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; } ll gcdf(ll a, ll b) { if (b == 0) { return a; } return gcdf(b, a % b); } int main() { ioinit(); ll b0, c0, b1, c1; cin >> b0 >> c0 >> b1 >> c1; c0 %= b0; if (c0 < 0) c0 += b0; c1 %= b1; if (c1 < 0) c1 += b1; ll g = gcdf(b0, b1); if (c0 > c1) { swap(b0, b1); swap(c0, c1); } ll dif = c1 - c0; if (dif % g != 0) { print("NaN"); return 0; } ll x, y; extgcd(b0, b1, x, y); y = -y; x *= dif / g; y *= dif / g; { ll p = 1e9; x -= p * b1 / g; y -= p * b0 / g; } { ll s = b0 * x + c0; ll t = b1 * y + c1; ll lcm = b1 * b0 / g; // s + lcm*p >= 0 // t + lcm*p >= 0 ll p = 0; if (s < 0) { p = max(p, (lcm - 1 - s) / lcm); } if (t < 0) { p = max(p, (lcm - 1 - t) / lcm); } x += p * b1 / g; y += p * b0 / g; // print(p, x, y); } { ll s = b0 * x + c0; ll t = b1 * y + c1; assert(s == t); assert(s >= 0); print(s); } return 0; }