sourceとsinkを追加し流量制限にa[i],b[i]を与えることで二部グラフのフローになることは本番中に気づいたが、YESだった場合に経路復元する方法が分からなかった。考えてみると、逆辺のcapはその辺に流したフローの量であるから、ここから容易に復元すること…

dp[i]をi以下の各自然数について素因数分解したときの素因数の個数の総和とすると、dp[a]-dp[b]が答えとなる。よって、前処理で素因数分解をしておけばいい。エラトステネスの篩をするときにsieve[i]にiの素因数のひとつ(最小や最大のものに固定することもで…

高速メビウス変換について自分が勉強した内容をまとめておく。証明はいい感じのサイトを参照のこと。 (http://d.hatena.ne.jp/simezi_tan/20130522/1369203086)集合に関する関数f,gについて次式が成り立つとき、g(S)が計算できているならば、任意のSについて…