例1 求$f(n)=\sum\limits_{1\le i\le n}[i\perp n]i^k$.

数据范围$1\le n\le 10^{12}, 0\le k\le 10$

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

 

容斥一下可以得到$f(n)=\sum\limits_{d|n}d^k\mu(d)\sum\limits_{i=1}^{\frac{n}{d}}i^k$.

当$k=0$时, $f(n)=\varphi(n)$.

当$k=1$时, $f(n)=\frac{1}{2}[n=1]+\frac{1}{2}n\varphi(n)$

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄