Baby Stepsなブログ

競プロとか。間違ったこと書いてあったら@pi0nep1oneにご連絡ください。

整数論

ARC 117 C - Tricolor Pyramid の mod3 まわりについての個人的な補足

問題 atcoder.jp 公式解説 atcoder.jp 解説にある通り、青白赤を0,1,2に対応させることで各ブロックは二項係数を使って最下段のブロックのから(二項係数の計算量は無視して)O(N)で求めることができるという問題。 この問題には更に 二項係数の計算において…

yukicoder バレンタインコンテスト2021 B Giri 解説

yukicoder.me 問題 1~nからn-1個を選んで作れる最小公倍数のうち、その最小値を求め、998244353で割った余りを求めよ。 前提 エラトステネスの篩 pione.hatenablog.com 解説 まず除外すべき1つの数は自明に、1~nの中の最大の素数である。 次にn-1個の数の…