結果
問題 | No.2119 一般化百五減算 |
ユーザー | t98slider |
提出日時 | 2022-11-05 06:22:57 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 22 ms / 2,000 ms |
コード長 | 2,645 bytes |
コンパイル時間 | 1,716 ms |
コンパイル使用メモリ | 171,736 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-19 02:34:00 |
合計ジャッジ時間 | 2,354 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 1 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 | 1 ms
5,376 KB |
testcase_09 | AC | 1 ms
5,376 KB |
testcase_10 | AC | 1 ms
5,376 KB |
testcase_11 | AC | 1 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 2 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 | 1 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 15 ms
5,376 KB |
testcase_21 | AC | 15 ms
5,376 KB |
testcase_22 | AC | 20 ms
5,376 KB |
testcase_23 | AC | 20 ms
5,376 KB |
testcase_24 | AC | 22 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; constexpr long long safe_mod(long long x, long long m) { x %= m; if (x < 0) x += m; return x; } constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) { a = safe_mod(a, b); if (a == 0) return {b, 0}; long long s = b, t = a; long long m0 = 0, m1 = 1; while (t) { long long u = s / t; s -= t * u; m0 -= m1 * u; auto tmp = s; s = t; t = tmp; tmp = m0; m0 = m1; m1 = tmp; } if (m0 < 0) m0 += b / s; return {s, m0}; } long long inv_mod(long long x, long long m) { assert(1 <= m); auto z = inv_gcd(x, m); assert(z.first == 1); return z.second; } ll N, M; std::pair<long long, long long> crt(const std::vector<long long>& r, const std::vector<long long>& m) { assert(r.size() == m.size()); int n = int(r.size()); long long r0 = 0, m0 = 1; for (int i = 0; i < n && m0 <= 1000000000; i++) { assert(1 <= m[i]); long long r1 = safe_mod(r[i], m[i]), m1 = m[i]; if (m0 < m1) { std::swap(r0, r1); std::swap(m0, m1); } if (m0 % m1 == 0) { if (r0 % m1 != r1) return {0, 0}; continue; } long long g, im; std::tie(g, im) = inv_gcd(m0, m1); long long u1 = (m1 / g); if ((r1 - r0) % g) return {0, 0}; long long x = (r1 - r0) / g % u1 * im % u1; r0 += x * m0; m0 *= u1; if (r0 < 0) r0 += m0; if(r0 > N)return {0, 0}; } return {r0, m0}; } long long floor_sum(long long n, long long m, long long a, long long b) { long long ans = 0; if (a >= m) { ans += (n - 1) * n * (a / m) / 2; a %= m; } if (b >= m) { ans += n * (b / m); b %= m; } long long y_max = (a * n + b) / m, x_max = (y_max * m - b); if (y_max == 0) return ans; ans += (n - (x_max + a - 1) / a) * y_max; ans += floor_sum(y_max, a, m, (a - x_max % a) % a); return ans; } int main(){ ios::sync_with_stdio(false); cin.tie(0); ll lcmv = 1; cin >> N >> M; vector<ll> B(M), C(M); for(int i = 0; i < M; i++){ cin >> B[i] >> C[i]; C[i] = (C[i] % B[i] + B[i]) % B[i]; } auto p = crt(C, B); if(p.first > N){ cout << "NaN" << '\n'; return 0; } for(int i = 0; i < M; i++){ if(p.first % B[i] != C[i]){ cout << "NaN" << '\n'; return 0; } } cout << p.first << '\n'; }