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

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

最大公約数

AtCoder ARC 105 B - MAX-=min (灰色, 300 点)

操作が「Euclid の互除法」っぽくなっている系の問題!!!そういう系の問題は次の一覧で示してる drken1215.hatenablog.com 問題へのリンク 問題概要 個の正の整数 に対して次の操作を繰り返し行う。 個の整数の最大値を 、最小値を とする。 なら手続きを…

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

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

New Year Contest 2015 L - 机のしみ

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

AOJ 3180 GCDMST (HUPC 2020 day3-I)

中盤枠という感じで作られた 問題へのリンク 問題概要 の番号を振られた 個の頂点があります。 最初、これらを繋ぐ辺はありません。 あなたはいくつかの辺を追加してこのグラフを連結にしたいと思いました。 頂点 と を繋ぐ辺を追加するには のコストがかか…

AtCoder ABC 162 C - Sum of gcd of Tuples (Easy) (灰色, 300 点)

素直に for 文を回して全部足せば OK!!! なお、3 つの整数の最大公約数の求め方に注意。 問題概要 を満たすすべての整数 の組に対しての、 の総和を求めよ。 制約 考えたこと 素直に 通りの組について、GCD を求めて合計しても間に合う。なお、3 つの整数…

Judge System Update Test Contest 202004 D - Calculating GCD (400 点)

面白かった 問題へのリンク 問題概要 要素からなる正の整数列 が与えられる。以下の 個のクエリに答えよ 各クエリは整数 が与えられる の順に、 という更新を行う 初めて となる瞬間の を求めよ 最終結果が 1 より大きいときは、その値を答えよ 制約 解法 (1…

AtCoder ABC 161 F - Division or Substraction (水色, 600 点)

めちゃくちゃ面白かった!!! 問題へのリンク 問題概要 整数 が与えられる。以下の条件を満たす 以上 以下の整数 の個数を求めよ。 整数 を用いて、 に対して操作を行っていく が で割り切れるならば を で置き換えて、そうでない場合には を に置き換える…

AtCoder AGC 018 A - Getting Difference (緑色, 300 点)

操作の仕方が Euclid の互除法そのものになっているタイプの問題。 問題へのリンク 問題概要 要素数 の数列 が与えられる。これに対して以下の操作を好きな回数だけ行うことができる: 整数を 2 つ選び、その差の絶対値をとり、それを数列に新たに挿入する 整…

Codeforces Round #201 (Div. 1) A. Alice and Bob (R1600)

シンプルで楽しい感じ 問題へのリンク 問題概要 要素からなる数列 がある (互いに相異なる)。交互に以下の操作を行う 数列から 2 つの整数を選んで、その差を数列の末尾に追加する ただし、「その差の値」がすでに数列中に含まれる場合は、この操作を行うこ…

Codeforces Round #626 (Div. 1) C. Instant Noodles

割と TLE に関して危険な橋をわたっていたのかもしれない。でも、ロリハとかしなくても大丈夫だった。 問題へのリンク 問題概要 左頂点数と右頂点数がともに であるような二部グラフが与えられる。二部グラフの辺数は である。 右頂点 には値 がある。今、左…

Educational Codeforces Round 81 D. Same GCDs (R1800)

教育的だと思ったのでメモだけ。 問題へのリンク 問題概要 整数 が与えられる。 以上 未満の整数 であって を満たすものの個数を求めよ。 解法 の最大公約数を として のオイラー関数値が答え。 #include <iostream> #include <sstream> #include <cstdio> #include <cstdlib> #include <cmath> #include <ctime></ctime></cmath></cstdlib></cstdio></sstream></iostream>…

AtCoder ABC 152 E - Flatten (水色, 500 点)

「〜の最小値を求めてください」「ただし 1000000007 で割ったあまりで」 ...この設定の歪さを見ると、不思議な気持ちになる 問題へのリンク 問題概要 個の正の整数 が与えられる。以下の条件を満たす正の整数列 をすべて考えたときの、 の最小値を求めよ (1…

Codeforces #613 (Div. 2) F. Classical? (R2800)

勉強になった...けど、これ知らずにできるもんなの!? 問題へのリンク あと、LCM の最小値バージョンもある! drken1215.hatenablog.com 問題概要 個の正の整数 が与えられる。これらから 2 個選んで LCM をとってできる 個の整数の最大値を求めよ。 制約 …

AtCoder ABC 150 D - Semi Common Multiple (青色, 400 点)

面白かった!!! 「2 で何回割れるのか」に着目するのはあるあるだけど、400 点としては難しめな感じかな。 問題へのリンク 問題概要 個の正の整数 と整数 が与えられる。以下の条件を満たす整数 が何個あるか求めよ。 任意の に対して、ある 0 以上の整数 …

第5回 ドワンゴからの挑戦状 予選 2018 E - Cyclic GCDs (赤色, 1000 点)

バチャでは手が回らなかったけど、復習した。ちょっとこの多項式解法は今はよくわからないけど、覚えておこう... 問題へのリンク 問題概要 要素の数列 が与えられる。 の順列 に対して、それを巡回群の直積として表したときの、各巡回群に含まれる要素に対応…

AOJ 2378 SolveMe (JAG冬合宿 2010 day3-J)

伝説の良難問。 現在でこそ AC 数 30 人で解説記事も豊富にあるが、当時は AC 数 3 人という状況で解説も無い中で、必死に 1 週間かけて通した想い出の問題。 問題へのリンク 問題概要 正の整数 と 以上の整数 が与えられる。 {} から {} への写像 の組であ…

AtCoder ABC 148 C - Snack (灰色, 300 点)

結構、そのまんまな問題が来ましたね。 問題へのリンク 問題概要 2 つの正の整数 が与えられる。 でも でも割り切れる正の整数のうち、最小の値を求めよ。 制約 考えたこと すごくそのまんまですね。 と の最小公倍数を求めよ、という問題。実は と の最大公…

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

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

AtCoder ABC 131 C - Anti-Division (茶色, 300 点)

「A 以上 B 以下の整数のうち〜を満たすものの個数を求めよ」という問題では (B 以下の整数のうちの〜を満たすものの個数) から (A-1 以下の整数のうちの〜を満たすものの個数) を引く とすると、すごくやりやすい!!!!! このテクニックは大昔の topcode…

Chokudai SpeedRun 002 J - GCD β (500 点)

「探索候補は実はそう多くない」という教育的問題!!! 問題へのリンク 問題概要 組の整数ペア がある。各ペアから整数をどちらかを選ぶ。こうして選ばれた 個の整数の最大公約数の最大値を求めよ。 制約 考えたこと 約数と言われて思い浮かべるべきことの…

AtCoder ABC 125 C - GCD on Blackboard (水色, 300 点)

累積和!累積和!累積和!!! でも累積和ならぬ累積 GCD なのと、左右両方から累積 GCD を求める。 問題へのリンク 問題概要 要素からなる数列 が与えられる。この数列に対して どれか一つ要素を選んで、 以下の好きな正の整数に書き換える という操作を行…

AOJ 2213 多項式の解の個数 (UTPC 2010 J)

今日の以下の類題 drken1215.hatenablog.com 解説はここに書いた。 qiita.com コード 形式的冪級数を用いてみた。 // // Formal Power Series (on runtime mod) // // verified: // Yosupo Judge // https://judge.yosupo.jp/problem/inv_of_formal_power_se…

Tenka1 2019 E - Polynomial Divisors (赤色, 800 点)

最大公約数を求めるときに abs つけてれば通ってた。。。 なにこれ悔しすぎる。。。 問題へのリンク 問題概要 次の整数係数多項式 が与えられる。任意の整数 に対して が で割り切れるような素数 をすべて求めよ。 制約 考えたこと めっちゃ好き!!!!!!…

Codeforces 552 DIV3 G. Minimum Possible LCM (R2400)

天才か!!! 問題へのリンク 問題概要 個の整数 が与えられる。 < となる であって、LCM() が最小となるものを求めよ。 制約 考えたこと という制約がいかにも怪しい。この制約が意味するのは 配列 a をバケットで表せる。すなわち a = (2, 3, 5) みたいな…

Codeforces #548 Div. 2 D - Steps to One (R2300)

これだった!!! drken1215.hatenablog.com もちろん高速ゼータ変換はいらなくて、愚直な包除原理で間に合う。 問題概要 整数 が与えられる。空の vector があって 以上 以下の整数の中から一様ランダムに 1 つ選び、 それを vector に push する このとき …

AtCoder AGC 001 B - Mysterious Light (500 点)

Euclid の互除法な操作過程をたっぷりと味わえる味わい深い問題。 問題へのリンク 問題概要 一辺の長さが の正三角形の図のような の地点からビームを発射する。このとき、既にビームが通ったところは新たに壁になる。ビームは必ず元の場所に戻ることが証明…

AOJ 3062 Product (RUPC 2019 day2-L)

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

AtCoder ABC 118 C - Monsters Battle Royale (茶色, 300 点)

教育的!!! 問題へのリンク 問題概要 個の正の整数 が与えられる。今、以下の操作を好きな回数だけ行う。 個から 2 つの正の整数 () を選んで、 を で置き換える この操作を行うと、最終的には 個の と 1 個の正の整数が残る。残る整数の最小値を求めよ。 …

AtCoder AGC 010 D - Decrementing (橙色, 1000 点)

一目見て惹かれた。すごく面白かった。割と自然な考察の流れで解けた。 問題へのリンク 問題概要 個の正の整数からなる数列 が与えられる。先手と後手が交互に以下を繰り返す。先に操作を行えなくなった方が負けである。双方最善を尽くしたときにどちらが勝…

QUPC 2018 I - Buffalo

楽しいけど重くて、重いけど楽しい 問題へのリンク 問題概要 要素から成る数列 が与えられる。 個から 2 個選んでできる 通りのペア のうち、以下の条件を満たすものを数え上げよ。 容量が の容器を用意して、以下の操作によって水の量 を汲み取れる 操作 1:…