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 f(x)=\sum_{x=1}^n \sum_{x|d} \mu(d/x)\times C_{cnt_x}^k\)
\(Ans=\sum_{d}\sum_{x|d}\mu(d/x)\times C_{cnt_x}^k\).