僕の以前書いた記事、共円がちょっと関係ある問題だ！！！！！！！！！！！！！
ガウス整数！！！！！！！！！！！！！！！！！！！

問題概要

二次元平面に関する以下の 3 種類のクエリ ( $Q$ 個) に答えよ

格子点 $(x, y)$ に石をおく
格子点 $(x, y)$ においてある石を取り除く
格子点 $(x, y)$ が指定されて、盤面全体の石の配置が 2 点 $(0, 0)$ と $(x, y)$ とを通る直線について線対称になるように、石を追加で置くことを考えたとき、そのために必要な石の個数を答えよ (実際に石を置くわけではない)

制約

$1 \le Q \le 2 × 10^{5}$
$1 \le x, y \le 112904$

考えたこと

$(x_1, y_1)$ と $(x_2, y_2)$ とが、ある原点を通る直線について線対称であるとき、

$x_1^{2} + y_1^{2} = x_2^{2} + y_2^{2}$

が成立する。そこで、問題を、各整数 $N$ に対して

$x^{2} + y^{2} = N$

ごとに独立に解くことを考える。そして今回は最悪でも $N \le 10^{10}$ 程度であり、この範囲内ではこれを満たす正の整数 $(x, y)$ の個数が $144$ 以下であることが示せる (共円でいうところの 576 角形定石)。

ボードゲーム「共円」に学ぶ、ガウス整数 x + yi の世界

に書いた複素整数の理論を使うとそれが示せる。結論として、

正の整数 $N$ に対して $x^{2} + y^{2} = N$ の解が存在する必要十分条件は、 $N$ を素因数分解したとき、すべての 4 で割って 3 あまる素因子について指数が偶数であることである。

またこの条件を満たすときの解の個数は、 $N$ を素因数分解したときの 4 で割って 1 あまる素因子の部分だけを $q_1^{e_1} q_2^{e_2} \dots q_k^{e_k}$ とするとき、 $4(e_1 + 1)(e_2 + 1) \dots (e_k + 1)$ 個である。

ということが示せる。

さて、各整数 $N$ に対して $x^{2} + y^{2} = N$ を満たす正の整数 $(x, y)$ が十分少ないことを利用した解法を考える。

points[N]: ノルムが $N$ な格子点を set に突っ込んだもの
nums[{x, y}]: 盤上の石のうち、2 点 $(0, 0)$ と $(x, y)$ とを通る直線に対して相方がいるような点の個数 (ここで $x, y$ は既約にしておく)
num: 置かれている点の個数

として、これらはクエリ 1, 2 に対して高々 144 個程度の更新でできる。クエリ 3 に対しては

num - nums[{x, y}]

を答えればよい ( $x, y$ は既約にする)。

#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;
using pll = pair<long long, long long>;

long long GCD(long long a, long long b) {
    if (b == 0) return a;
    else return GCD(b, a % b);
}

void normalize(long long &a, long long &b) {
    long long g = GCD(a, b);
    a /= g, b /= g;
}

int main() {
    int Q; scanf("%d", &Q);
    map<long long, set<pll> > points;
    map<pll, int> nums;
    long long num = 0;
    for (int _ = 0; _ < Q; ++_) {
        int t; long long x, y;
        scanf("%d %lld %lld", &t, &x, &y);
        if (t == 1) {
            long long N = x*x + y*y;
            for (auto p : points[N]) {
                long long nx = p.first + x;
                long long ny = p.second + y;
                normalize(nx, ny);
                nums[pll(nx, ny)] += 2;
            }
            points[N].insert(pll(x, y));
            normalize(x, y);
            nums[pll(x, y)]++;
            ++num;
        }
        else if (t == 2) {
            long long N = x*x + y*y;
            points[N].erase(pll(x, y));
            for (auto p : points[N]) {
                long long nx = p.first + x;
                long long ny = p.second + y;
                normalize(nx, ny);
                nums[pll(nx, ny)] -= 2;
            }
            normalize(x, y);
            nums[pll(x, y)]--;
            --num;
        }
        else {
            normalize(x, y);
            printf("%lld\n", num - nums[pll(x, y)]);
        }
    }
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Codeforces AIM Tech Round (Div. 1 + Div. 2) 5 F. Make Symmetrical (R2900)

問題概要

制約

考えたこと