因为模拟赛太频繁已经很久没有写闲话了
今天搜到的一道 IMO Shortlist 题，挺水的，但是还挺好玩
先反演一波：
\[a_n=\sum_{d | n}2^d\mu(\frac nd) \]然后因为 \(\mu\) 和 \(2^n\) 都是积性的，所以 \(a_n\) 是积性的，只需要考虑素数幂处的取值即可
\[a_{p^k}=\sum_{i=0}^{k}2^{p^i}\mu(p^{k-i})=2^{p^k}-2^{p^{k-1}} \]所以证明 \(2^{p^k}-2^{p^{k-1}} | p^k\) 即可，即要证明：
\[2^{p^k} \equiv 2^{p^{k-1}}\pmod {p^k} \]考虑欧拉定理，\(\gcd(2,p^k)=1\) 除了 \(p=2\) 时均成立，所以先特判掉 \(p=2\) 的情况继续转换：
\[\begin{aligned} p^k &\equiv p^{k-1}\pmod {\varphi(p^k)}\\ p^k &\equiv p^{k-1}\pmod {p^{k}-p^{k-1}}\\ p^{k-1} &\equiv p^{k-1}\pmod {p^{k}-p^{k-1}}\\ \end{aligned} \]然后就证完了
标签：pmod,闲话,sum,mu,积性,8.23,equiv From： https://www.cnblogs.com/Rolling-star/p/17652531.html