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

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

最大公約数

AtCoder ABC 212 G - Power Pair (黄色, 600 点)

原始根が絡む問題は時々出るイメージですね。 問題へのリンク 問題概要 素数 が与えられます。 次の条件を満たす整数 の組の個数を 998244353 で割ったあまりを求めてください。 ある正の整数 が存在して、 が成立する 制約 は素数 考えたこと 整数問題とい…

AtCoder ABC 206 E - Divide Both (青色, 500 点)

約数系包除原理の教育的問題 問題へのリンク 問題概要 整数 が与えられるので、以下の条件を満たす整数 の組の個数を求めてください。 としたとき、, , 制約 解法 (1):約数系包除 まさに約数系包除原理の教育的良問。この問題をきっかけとして、次の記事を…

JOI 本選 2007 E - 最軽量のモビール (AOJ 0520, 難易度 7)

読解が大変だけど、本質的には木 DP な問題 ジャッジへのリンク AOJ ページ 問題概要 本の棒を用いて、下図のようなモビールを作りたい。 入力としては、各棒 についての 左端から支点までの長さ 右端から支点までの長さ 左端からつながっている棒の index (…

AtCoder ABC 186 E - Throne (水色, 500 点)

一次合同方程式を解く問題です! 問題へのリンク 問題概要 円周上に 個の椅子が並べられています。そのうち 1 つは玉座です。 高橋君は最初、玉座から時計回りに数えて 個隣の椅子に座っており、次の行動を繰り返します。 行動:いま座っている椅子から時計…

AOJ 3217 Cafe au lait (OUPC 2020 I)

数学っぽい問題好き!!! 問題へのリンク editorials 問題概要 個のカフェオレがある。 番目のカフェオレは、コーヒーが mg、ミルクが mg だけ入っている (ともに整数)。 これらを混ぜて作れるカフェオレのうち、コーヒー量 とミルク量が がともに正の整数…

AtCoder ARC A - Redundant Redundancy (灰色, 300 点)

言語「text (cat)」で AC を取れる数少ない問題の一つ 問題へのリンク 問題概要 正の整数 が与えられる。 のどれで割っても 1 あまる整数 ( 以上 以下) を一つ求めよ。 制約 解法 (1) の最大公倍数を として、 が答えになる。似た発想をする問題として、次の…

AtCoder AGC 046 A - Takahashikun, The Strider (灰色, 200 点)

面白かった。久しぶりの最大公約数ゲー。 問題へのリンク 問題概要 平面上に高橋君がおり、真北を向いて立っています。 高橋君が以下の行動を 回繰り返したときに元の位置に戻ってくるような最小の正の整数 を求めてください。 今向いている方向に 1 メート…

CodeChef Practice(Easy) GCD Sum

添字 GCD 畳み込みの練習問題! 問題へのリンク 問題概要 長さ の正整数列が 個ある。 各数列から高々 1 個ずつ整数を抜き取って得られる数列は 通り考えられる。そのうち抜き取られた数値が 2 個以上あるようなものすべてについての、「それらの数値の最大…

AtCoder AGC 038 C - LCMs (黄色, 700 点)

添字 GCD convolution が一躍話題になった問題だった気がする 問題へのリンク 問題概要 長さ の整数列 がある。 の値を 998244353 で割ったあまりを求めよ。 制約 考えたこと 個の値のうちのすべてのペアに対するなにかの総和を求める問題では を満たす につ…

AtCoder ABC 177 E - Coprime (緑色, 500 点)

結構教育的!! 問題へのリンク 問題概要 個の正の整数 が与えられる。 これらのうちのどの 2 つも互いに素であるとき、"pairwise coprime" そうではなく 個の最大公約数が 1 であるとき、"setwise coprime それ以外のとき、"not coprime" と出力せよ。 制約…

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 (R2300)

割と 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) (1200 点)

伝説の良難問。 現在でこそ 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 点)

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