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。。。
哦对了这个函数貌似叫做除数函数，表示约数的次幂和。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include <bits/stdc++.h> #define maxn 64000010 #define inf 0x3f3f3f3f #define REP(i,x,y) for(int i=x;i<(y);i++) #define RREP(i,x,y) for(int i=x;i>(y);i--) using namespace std; typedef long long ll; typedef pair<int,int> pii; ll divisor_2[maxn],minprime[maxn]; bool notprime[maxn]; vector<ll>prime; void sieve(){ for(int i=2;i<=64000000;i++) { if(notprime[i]==0) { prime.push_back(i); divisor_2[i]=1+1LL*i*i; minprime[i]=1+1LL*i*i; } // printf("%d",i); for(int j=0;j<prime.size()&&1LL*i*prime[j]<=64000000;j++) { notprime[i*prime[j]]=1; if(i%prime[j]==0) { minprime[i*prime[j]]=minprime[i]*prime[j]*prime[j]+1; divisor_2[i*prime[j]]=divisor_2[i]/minprime[i]*minprime[i*prime[j]]; break; } else { divisor_2[i*prime[j]]=divisor_2[i]*divisor_2[prime[j]]; minprime[i*prime[j]]=divisor_2[prime[j]]; } } } } int main() { sieve(); ll sum=0; for(int i=1;i<64000000;i++){ ll tmp=sqrt(divisor_2[i]); if(tmp*tmp==divisor_2[i]) sum+=i; } cout<<sum<<endl; } |