約数の個数は少ない
原始根が絡む問題は時々出るイメージですね。 問題へのリンク 問題概要 素数 が与えられます。 次の条件を満たす整数 の組の個数を 998244353 で割ったあまりを求めてください。 ある正の整数 が存在して、 が成立する 制約 は素数 考えたこと 整数問題とい…
この回の前の回の LCMs といい、約数系包除がこの時期流行ってたのかな。 問題へのリンク 問題概要 整数 が与えられる。 以上 以下のすべての整数 に対し、 に以下の操作を繰り返すことによって次に に戻るまでの操作回数 (戻らない場合 0) を足し合わせた値…
中国剰余定理使う問題楽しいよね! 問題へのリンク 問題概要 正の整数 が与えられる。以下の条件を満たす最小の正の整数 を求めよ。 が の倍数である 制約 考えたこと まず、 なので、問題の条件は次と同値になる。 が の倍数である ここで改めて を で置き…
LIS の亜種だけど、雰囲気違って面白い! 問題へのリンク 問題概要 長さ の正の整数列 が与えられる。この部分列であって 狭義単調増加 後の index に出てくるやつは前の index にでてくるやつの倍数になっている という条件を満たすものの最長の長さを求め…
「探索候補は実はそう多くない」という教育的問題!!! 問題へのリンク 問題概要 組の整数ペア がある。各ペアから整数をどちらかを選ぶ。こうして選ばれた 個の整数の最大公約数の最大値を求めよ。 制約 考えたこと 約数と言われて思い浮かべるべきことの…