結果
問題 | No.849 yuki国の分割統治 |
ユーザー |
|
提出日時 | 2019-07-05 23:21:13 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 79 ms / 2,000 ms |
コード長 | 1,236 bytes |
コンパイル時間 | 2,370 ms |
コンパイル使用メモリ | 205,116 KB |
最終ジャッジ日時 | 2025-01-07 06:10:38 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> using namespace std; tuple<int, int, int> ext_gcd(int a, int b) { if (!b) return {1, 0, a}; int x, y, g; tie(x, y, g) = ext_gcd(b, a % b); return {y, x - a / b * y, g}; } signed main() { ios::sync_with_stdio(false); int A, B, C, D; cin >> A >> B >> C >> D; if (C < A) swap(A, C), swap(B, D); int N; cin >> N; map<pair<long long, long long>, int> gcnt; int gx, xx, yy; tie(xx, yy, gx) = ext_gcd(A, C); int gy = __gcd(B, D); if (!gx || !gy) { for (int i = 0; i < N; ++i) { long long x, y; cin >> x >> y; if (gx) { x %= gx; if (x < 0) x += gx; } if (gy) { y %= gy; if (y < 0) y += gy; } ++gcnt[make_pair(x, y)]; } } else { for (int i = 0; i < N; ++i) { long long x, y; cin >> x >> y; if (gx <= x) { long long k = (x - 1) / gx; x -= k * gx; y -= 1LL * k * (1LL * xx * B + 1LL * yy * D); } long long zero = 1LL * A / gx * D - 1LL * C / gx * B; if (zero) { if (zero < 0) zero *= -1; y %= zero; if (y < 0) y += zero; } ++gcnt[make_pair(x, y)]; } } cout << gcnt.size() << endl; return 0; }