結果

問題 No.849 yuki国の分割統治
コンテスト
ユーザー MICHAEL
提出日時 2026-07-21 17:25:44
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.90.0)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 62 ms / 2,000 ms
+ 722µs
コード長 1,839 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,399 ms
コンパイル使用メモリ 356,400 KB
実行使用メモリ 5,888 KB
最終ジャッジ日時 2026-07-21 17:25:51
合計ジャッジ時間 5,549 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 200005;
struct P {
    LL x, y;
};
P a[maxn];
bool cmp(P p, P q) {
    if (p.x != q.x) return p.x < q.x;
    return p.y < q.y;
}
LL LLabs(LL x) {
    return x < 0 ? -x : x;
}
LL gcd_func(LL x, LL y) {
    x = LLabs(x);
    y = LLabs(y);
    while (y) {
        LL r = x % y;
        x = y;
        y = r;
    }
    return x;
}
int main() {
    LL a1, b1, c1, d1;
    cin >> a1 >> b1 >> c1 >> d1;
    int n;
    cin >> n;
    LL h11 = a1, h21 = b1, h12 = c1, h22 = d1;
    while (h12 != 0) {
        LL q = h11 / h12;
        LL r1 = h11 - q * h12;
        LL r2 = h21 - q * h22;
        h11 = h12; h21 = h22;
        h12 = r1; h22 = r2;
    }
    if (h11 < 0) {
        h11 = -h11;
        h21 = -h21;
    }
    if (h11 == 0) {
        LL g = gcd_func(h21, h22);
        h21 = 0;
        h22 = g;
    } else {
        if (h22 < 0) h22 = -h22;
        if (h22 > 0) {
            h21 = (h21 % h22 + h22) % h22;
        }
    }
    for (int i = 1; i <= n; i++) {
        LL x, y;
        cin >> x >> y;
        if (h11 == 0) {
            a[i].x = x;
            if (h22 > 0) {
                a[i].y = (y % h22 + h22) % h22;
            } else {
                a[i].y = y;
            }
        } else {
            LL rx = (x % h11 + h11) % h11;
            LL k = (x - rx) / h11;
            __int128 tmp = y - (__int128)k * h21;
            a[i].x = rx;
            if (h22 > 0) {
                a[i].y = (LL)((tmp % h22 + h22) % h22);
            } else {
                a[i].y = (LL)tmp;
            }
        }
    }
    sort(a + 1, a + n + 1, cmp);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (i == 1 || a[i].x != a[i - 1].x || a[i].y != a[i - 1].y) {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}
0