codevs 2606 约数和问题

看到这道题我们首先考虑线性筛。然而？？？2*10^9直接跪掉。

考虑每个因子i对答案的贡献，为[n/i]*i。那么？分块处理即可。

#include<iostream>
#include<cstdio>
using namespace std;
long long x,y;
long long ans=0;
long long work(long long n)
{
ans=0;
long long i=1;
while (i<=n)
{
long long j=n/(n/i);
ans=ans+(n/i)*((j*j+j+i-i*i)/2);
i=j+1;
}
return ans;
}
int main()
{
scanf("%lld%lld",&x,&y);
printf("%lld\n",work(y)-work(x-1));
return 0;
}

codevs 2606 约数和问题

原文：http://www.cnblogs.com/ziliuziliu/p/5170479.html