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

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

Codeforces AIM Tech Round 5 F - Make Symmetrical

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

問題へのリンク

問題概要

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

  1. 格子点  (x, y) に石をおく
  2. 格子点  (x, y) においてある石を取り除く
  3. 格子点  (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 角形定石)。

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


正の整数  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)]);
        }
    }
}