用欧拉函数反演?

可爱即是正义 · 2018-08-19 11:42:04 · 个人记录

例题：P3768

留一个比较好的博客

题意就是求

(\sum_{i=1}^{n}\sum_{j=1}^{n}ijgcd(i,j))modp的值

2.首先有一条结论：一个数的所有因子的欧拉函数之和等于这个数本身。

用式子说就是id=\sum_{d|n}φ(d)id=φ*1

所以上式可以转成\sum_{i=1}^{n}\sum_{j=1}^{n}ij\sum_{k|gcd(i,j)}φ(k)

变换枚举顺序\sum_{k=1}^{n}φ(k)\sum_{k|i}\sum_{k|j}ij

枚举k的倍数i,j\sum_{k=1}^{n}φ(k)k^{2}(\sum_{i=1}^{n/k}i)^{2}

然后推到\sum_{k-1}^{n}φ(k)k^{2}\sum_{i=1}^{n/k}i^{3}

是个结论，证明