結果
問題 | 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;}