GDKOI2021普及组Day3C数论
2220+
作者：crxis 发布：2021-02-03 分类：数学
题目大意：已知n=∏peii，λ(n)=−1∑ei，求k∑k=1∑i|k∑j|iλ(i)λ(j)。
解题思路
首先，理解公式求的是什么，写个暴力程序验证一下：
然后，花一点点时间，改成O(n√n)算法，主要是枚举约数的优化、17-20行的记忆化。
打表发现跟完全平方数有关系？推出答案是n∑i=1ni2。
公式推导：k∑k=1∑i|k∑j|iλ(i)λ(j)=k∑k=1∑i|kλ(i)∑j|iλ(j)
如果i不是完全平方数，那么会有奇数次幂，他的约数可以选这个质数的0次方和1次方、2次方和3次方……奇数部分的约数和偶数部分的约数的λ(j)值一个加一个减可以互相抵消。
如果i是完全平方数，每个次幂都是偶数，如1次方和2次方、3次方和4次方……可以互相抵消，最后剩下0次方，即λ(1)=1。
因此，λ(i)∑j|iλ(j)当i是完全平方数的时候加1，不是完全平方数的时候值为零。
这样，问题就转化成求1以内的完全平方数+2以内的完全平方数+3以内的完全平方数+…+n以内的完全平方数。
最后，我们可以考虑每个完全平方数的贡献，1共加n/1次，4共加n/4次……
