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()……メビウス関数。
つまり、nの約数であるすべてのdについて、mu(n/d)*2^(d-1)の総和を求めたいらしい。
また、包徐原理を使うことで、2^(n-1)からd>1となるa(d)を引いても求められるらしい。
和がn/dだったときに(a,b,c)だったのがd倍すると(ad,bd,cd)となるからかなあ。
