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

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

拡張Euclidの互除法

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

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

AtCoder AGC 026 B - rng_10s (600 点)

あーーーーーー、これは大好物系なん!!!!! 本番でやってみたかったん!!!!! 問題へのリンク 問題概要 (AGC 026 B) 整数 があたえられる。 最初は在庫に 個あって、 毎日 個ずつ消費される その日の最後に 個以下しか残っていなかったら 個補充され…