H.雪莱的式子_牛客博客

分析题目意思，可以把式子抽象为 $k$ 个人从 $S(n)$ 这个集合里面选数字,由于莫比乌斯函数有平方因子的贡献都是0，所以可以认为是一个质数的幂最多出现一次,此时当出现的不同质数个数为奇数时，贡献是 $-1$ ,偶数时,贡献为 $1$

考虑枚举出现了多少个不同的质数,则贡献为

\sum_{i=0}^{n}(-1)^{i} \cdot C_{n}^{i} \cdot k^{i}

即，先组合数计算 $n$ 个质数中选了哪 $i$ 个，选出以后对于每个质数，他都可能来自 $k$ 个人中的一个，即 $k^{i}$

考虑二项式定理

(a b)^{n} = \sum_{i=0}^{n} C_{n}^{i} \cdot a^{i} \cdot b^{n-i}

令 $a = k$ , $b = -1$ 得到原式就等于

(k-1)^{n} \cdot (-1)^{2i-n}

快速幂即可