競技プログラミングにおける問題解決戦略
数理的考察に基づくアルゴリズム設計について議論する。以下に代表的な問題パターンとその解法を示す。
「CF1183F Topforces Strikes Back」
最大値選択問題の最適化戦略を検討する。以下の条件を満たす組み合わせを探索する：
単一要素：最大値を選択
二要素：最大値の因数である必要がある
三要素：最大値とその約数の組み合わせ
証明概要
最大値以外の要素を含む場合 ...
9月22日 08:08 投稿
min25筛と洲閣筛
min25筛
ある積性関数 f(x) が与えられ、f(p) が素数 p に関する多項式で、かつ f(pk) が高速に計算できる場合、sumi=1n f(i) を求める。
例：n = 1010 に対して sumi=1n σ0(ik) を求める。
ステップ1：素数の積性関数の前処理和
1 から n までの素数の個数を求める。
f(n, m) を、2 から n までの数のうち、素数であるか、または最小の素因数が p1, ..., pm (pi は i 番 ...
6月1日 21:05 投稿