結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0