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

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

ベズーの等式

TTPC 2023 E - R-Connected Components

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

AtCoder ABC 210 E - Ring MST (青色, 500 点)

また 1 つ、MST 系の問題のストックが増えた。でも実質的には整数問題だった。 問題へのリンク 問題概要 頂点数 、辺数 のグラフがある。このグラフに以下の操作 を実施することで重み付き無向グラフを作る。 に対して、頂点 と頂点 % の間に、重み の辺を張…

yukicoder No.2066 Simple Math !

floor sum のいい感じの練習問題! 問題へのリンク 問題概要 正整数 が与えられる。 非負整数 を用いて という形で表せる正の整数のうち、 番目に小さいものを求めよ。 ( 個の入力ケースが与えられる) 制約 考えたこと いかにも二分探索という問題。次の判定…

AtCoder ABC 142 D - Disjoint Set of Common Divisors (緑色, 400 点)

すごく楽しくて教育的な整数問題 問題へのリンク 問題概要 2 つの正の整数 が与えられる。 の公約数から何個か整数を選ぶことを考える。 選んだ整数からどの 2 つをとっても、それらが互いに素になるようにしたい。 選べる個数の最大値を求めよ。 制約 考え…

AOJ 3062 Product (RUPC 2019 day2-L)

本当に悔しい。BSGS に無限にこだわってしまった。なぜ方針転換を図れなかったのか。。。 そしてこの問題、本当に本当に整数論の魅力がたっぷり詰まった楽しい問題だった。作問してくれた会津大チームにすごく感謝!!!!!!!!!! 問題へのリンク 問題…