結果
問題 | No.2119 一般化百五減算 |
ユーザー |
![]() |
提出日時 | 2024-04-07 03:54:55 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,888 bytes |
コンパイル時間 | 2,788 ms |
コンパイル使用メモリ | 250,192 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-01 04:22:22 |
合計ジャッジ時間 | 4,305 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 WA * 3 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;#ifdef LOCAL#include <debug_print.hpp>#define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)#else#define debug(...) (static_cast<void>(0))#endif// ax + by = gcd(a, b) を満たす x, y を求めるpair<ll, ll> extgcd(ll a, ll b) {if(b == 0) return {1, 0};auto [y, x] = extgcd(b, a % b);y -= a / b * x;return {x, y};}// x ≡ r[i] (mod m[i]) を解き, x ≡ r0 (mod. m0) となる (r0, m0) を返す// m0 := lcm(m[0], m[1], ...)pair<ll, ll> crt(const vector<ll>& r, const vector<ll>& m) {assert(r.size() == m.size());int n = r.size();ll r0 = 0, m0 = 1;for(int i = 0; i < n; i++){assert(1 <= m[i]);ll r1 = (r[i] % m[i] + m[i]) % m[i], m1 = m[i], g = gcd(m0, m1);// p * m0 + q * m1 = g となる (p, q) を求める// このとき p は p * m0 / g ≡ 1 (mod. m1 / g) を満たすauto [p, q] = extgcd(m0, m1);// r1 ≡ r0 (mod. g) でない場合は解なしif((r1 - r0) % g != 0) return {-1, 0};// s = (r1 - r0) / g として両辺に s を掛けて// p * m0 * s + q * m1 * s = r1 - r0 とする// x = r0 + m0 * p * s (= r1 - m1 * p * s) とすると// x ≡ r1 (mod. m1), x ≡ r0 (mod. m0) を満たすll u1 = m1 / g;ll x = (r1 - r0) / g % u1 * p % u1;r0 += m0 * x;m0 *= u1; // lcm(m0, m1) = m0 * m1 / g}r0 = (r0 % m0 + m0) % m0;return {r0, m0};}int main(){cin.tie(nullptr);ios::sync_with_stdio(false);cout << fixed << setprecision(20);int N, M;cin >> N >> M;vector<ll> B(M), C(M);for(int i = 0; i < M; i++) cin >> B[i] >> C[i];auto [r, m] = crt(C, B);if(r == -1 || r > N) {cout << "NaN" << endl;}else{cout << r << endl;}}