Codeforces Round #428 (Div. 2) D. Winter is here

Problem - D - Codeforces

自分で見返したときにわかるようなメモ書き。

f(x) := gcdがxの倍数になるような全てのクランの強さの総和 g(x) := gcdがちょうどxになるような全てのクランの強さの総和

とすると、f(x), g(x)は以下のように計算できる。

f(x) = \displaystyle \sum_{k=0}^{x} {k \displaystyle \binom {x}{k}} = 2^{x-1}x

g(x) = f(x) - \displaystyle \sum_{i=2}^{\infty} g(ix)

ここまでくれば答えは\displaystyle \sum_{x=2}^{\infty} g(x)xで求まる。

gist.github.com

f(x)の計算はwolframalphaに本番は投げたが、他の参加者のブログを見ると(1+x)^{n}微分から導出できるらしい。
Wolfram|Alpha: Computational Knowledge Engine

(1+x)^{n}を展開して微分すると\sum_{k=1}^{n} k \displaystyle \binom {n}{k}x^{k-1}になり、x=1を代入すると求めたい式と一致する。(1+x)^{n}微分してx=1を代入すると2^{n-1}nとなる。

よって\sum_{k=1}^{n} k \displaystyle \binom {n}{k} = 2^{n-1}n