競プロで Σi*f(i) を求める問題

競プロで Σi*f(i) （ Σi/f(i) でもよい）を求める問題で、f(i)のとる値が少ない場合、「f(i)の値ごとにiの総和を求めてからf(i)をかけて、それらをすべて足す」というテクを使えばよいという知見を得た。

最近解いた問題でいうと、yukicoder No.737 PopCount（No.737 PopCount - yukicoder） と ABC020 D LCM Rush（D - LCM Rush） はこの考え方を使うと解ける。

PopCount の桁DP解法は popcount(i) の値が j になるような i の総和を桁DPで求めて j をかけるということをしてる。
（参考：http://kmjp.hatenablog.jp/entry/2018/09/28/0900）

LCM Rush は Σlcm(i,K) = K Σi/gcd(i,K) という言い換えをしたあと、Σi/gcd(i,K) を求めるところで、 gcd(i,K) の値が j になるような i の総和を包除原理を使って求めて j で割るということをしてる。
（参考：AtCoder Beginner Contest 020 D: LCM Rush - hogecoder）