月度归档:2018年04月

Project Euler 211 Divisor Square Sum(约数平方和)

For a positive integer n, let σ2(n) be the sum of the squares of its divisors. For example,

σ2(10) = 1 + 4 + 25 + 100 = 130.
Find the sum of all n, 0 < n < 64,000,000 such that σ2(n) is a perfect square.

简单写写了,早上问了一下大爷们约数平方和有什么好的性质么?答:积性函数啊!哦,那我只要线性筛一遍一个个验证答案好了。。。
然后发现自己原来没怎么学过线性筛啊。。。


如果x=p1^a1*p2^a2*….pk^ak,


那么约数平方和为(1+p1^2+p1^4+…+p1^(2*a1))(1+p2^2+p2^4+…p2^(2*a2))*…*(1+pk^2+pk^4+…+pk^(2*ak))。
那么为了保证线性筛的复杂度,我们需要存一个每个数的最小素因子(也就是p1)的括号里的东西就可以做了。。。
直接看代码好了~
注意爆int。。。
哦对了这个函数貌似叫做除数函数,表示约数的次幂和。