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

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

ガウス整数

TTPC 2023 E - R-Connected Components

大好き!!ガウス整数の問題リストがまた 1 個増えた! 問題へのリンク 問題概要 1 つの正の整数 が与えられる。 二次元平面上の任意の格子点を頂点としたグラフにおいて、距離の平方が であるような 2 点間に辺を張っていく。 こうしてできたグラフの連結成…

yukicoder No.321 (P,Q)-サンタと街の子供たち

kirika さんの「整数論テクニック集」より。 問題へのリンク 問題概要 二次元平面平面上において から の合計 8 方向に移動できる。今、 個のクエリが与えられる。各クエリは座標 が与えられる。原点から出発して、上述の移動を好きな順序で好きな回数だけ繰…

New Year Contest 2015 L - 机のしみ

ガウス整数が使える問題と聞いて!!! 問題へのリンク editorial 問題概要 二次元平面上に 個の格子点 がある。これに最小個数の格子点を追加することで、格子点全体が「正方形グリッド」の模様を形作るようにしたい。追加すべき格子点の個数を求めよ。 制…

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

僕の以前書いた記事、共円がちょっと関係ある問題だ!!!!!!!!!!!!! ガウス整数!!!!!!!!!!!!!!!!!!! 問題へのリンク 問題概要 二次元平面に関する以下の 3 種類のクエリ ( 個) に答えよ 格子点 に石をおく 格子点 においてあ…

AtCoder AGC 025 D - Choosing Points (赤色, 800 点)

二部グラフ解法頭いいと思ったものの、整数論的考察で通したのでその報告を。TL 見た限りだと、kirika さんと同じ解法っぽいですがかなり少数派っぽいです (ただし、自分はイデアルという概念を意識できてはいなかったです...)。 d1=2^k * u (u は奇数) とす…