結果
問題 |
No.321 (P,Q)-サンタと街の子供たち
|
ユーザー |
|
提出日時 | 2023-10-17 14:21:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 93 ms / 2,000 ms |
コード長 | 2,123 bytes |
コンパイル時間 | 2,019 ms |
コンパイル使用メモリ | 196,032 KB |
最終ジャッジ日時 | 2025-02-17 08:10:36 |
ジャッジサーバーID (参考情報) |
judge1 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; struct gaussian_integer { using gint = gaussian_integer; ll x, y; gaussian_integer() : x(0), y(0) {} gaussian_integer(ll x) : x(x), y(0) {} gaussian_integer(ll x, ll y) : x(x), y(y) {} friend ll abs(const gint& a) { return a.x * a.x + a.y * a.y; } friend gint conj(const gint& a) { return gint(a.x, -a.y); } gint operator-() { return gint(-x, -y); } gint operator+(const gint& r) { return gint(*this) += r; } gint operator-(const gint& r) { return gint(*this) -= r; } gint operator*(const gint& r) { return gint(*this) *= r; } gint operator/(const gint& r) { return gint(*this) /= r; } gint operator%(const gint& r) { return gint(*this) %= r; } gint& operator+=(const gint& r) { x += r.x, y += r.y; return *this; } gint& operator-=(const gint& r) { x -= r.x, y -= r.y; return *this; } gint& operator*=(const gint& r) { std::tie(x, y) = std::make_pair(x * r.x - y * r.y, x * r.y + y * r.x); return *this; } gint& operator/=(const gint& r) { assert(not(r.x == 0 and r.y == 0)); auto near = [](ll a, ll b) { ll q = a / b, r = a - q * b; if(abs(r) > abs(r - b)) return q + 1; if(abs(r) > abs(r + b)) return q - 1; return q; }; gint u = (*this) * conj(r); return *this = gint(near(u.x, abs(r)), near(u.y, abs(r))); } gint& operator%=(const gint& r) { return *this -= (*this) / r * r; } bool operator==(const gint& r) { return x == r.x and y == r.y; } bool operator!=(const gint& r) { return x != r.x or y != r.y; } friend gint gcd(gint a, gint b) { if(b == gint(0, 0)) return a; return gcd(b, a % b); } }; int main() { using gint = gaussian_integer; gint t; cin >> t.x >> t.y; gint g = gcd(t, conj(t)); int N; cin >> N; int ans = 0; while(N--) { gint v; cin >> v.x >> v.y; if(g == gint(0, 0)) { if(v == gint(0, 0)) { ans++; } } else { if(v % g == gint(0, 0)) { ans++; } } } cout << ans << endl; }