結果

問題 No.321 (P,Q)-サンタと街の子供たち
ユーザー rogi52
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0