olpheの競プロ帖

競プロ問やアルゴリズム等の考察します

2017-12-12から1日間の記事一覧

Codeforces Round #450 (Div. 2) D問題

和がNで数列の全要素のGCDが1となる数列の数を求めたい。 a(n) = sum_{d|n} mu(n/d)*2^(d-1) この式で表せるらしいが全然意味が分からなかったのでメモしておく。 d | n……dはnの約数という意味。 sum_{ }……{ }内のすべての要素について何か処理をする。 mu()…