CF645F
我们可以计算这样的函数 \(F(x)\) 表示 \(\gcd\) 是 \(x\) 的倍数有多少个 \(k\) 元组。
设 \(x\) 的倍数有 \(cnt_x\) 个数，那么 \(F(x)=C_{cnt_x}^k\)。
根据莫反，\(f(x)=\sum_{x|d} F(d)\mu (d/x)\)
\(Ans=\sum xf(x)=\sum_{x=1}^n x \sum_{x|d} \mu(d/x)\times C_{cnt_d}^k\)
枚举 \(d\)，\(Ans=\sum_{d=1}^n C_{cnt_d}^k \sum_{x|d} \mu(d/x) x\).
观察到 \(\sum_{x|d} \mu(d/x) x= \varphi(d)\)，可以直接预处理。
且每次加入一个数，最多带来 \(\sqrt\) 个 \(cnt\) 的改变，直接暴力维护，复杂度 \(O(n\sqrt n)\).