链接:http://acm.hdu.edu.cn/showproblem.php?pid=3501
求一个数n的所有小于它并且与它不互质的数的和。
打算复习一波欧拉函数的,结果这题发现可以容斥。
我们知道如果一个数n含有因数x,那么x的倍数都和n不互质,且质因数至少为x。
我们可以知道,对于任意小于n的因数x,对本题的贡献为x+2x+3x+…+kx=k(k+1)2x,其中k为n对x的倍数。
于是直接对n分解因数,再容斥。
1 |
|
再来考虑欧拉函数,知道一个定理:小于n的数,且与n互质的数的和为:
ϕ(n)×n2
然而小于n的数的和为n(n−1)2,于是我们一减:
n(n−1−ϕ(n))2
1 | signed main() { |
v1.5.2