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

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

この回の前の回の LCMs といい、約数系包除がこの時期流行ってたのかな。 問題へのリンク 問題概要 整数 が与えられる。 以上 以下のすべての整数 に対し、 に以下の操作を繰り返すことによって次に に戻るまでの操作回数 (戻らない場合 0) を足し合わせた値…

AtCoder AGC 039 C - Division by Two with Something (黄色, 800 点)

中国剰余定理使う問題楽しいよね！ 問題へのリンク 問題概要 正の整数 が与えられる。以下の条件を満たす最小の正の整数 を求めよ。 が の倍数である 制約 考えたこと まず、 なので、問題の条件は次と同値になる。 が の倍数である ここで改めて を で置き…

ACL Contest 1 B - Sum is Multiple (青色, 600 点)

LIS の亜種だけど、雰囲気違って面白い！ 問題へのリンク 問題概要 長さ の正の整数列 が与えられる。この部分列であって 狭義単調増加 後の index に出てくるやつは前の index にでてくるやつの倍数になっている という条件を満たすものの最長の長さを求め…

yukicoder No.979 Longest Divisor Sequence

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

Chokudai SpeedRun 002 J - GCD β (500 点)