Fear Factoring_牛客博客

http://codeforces.com/group/NVaJtLaLjS/contest/242532
The Slivians are afraid of factoring; it’s just, well, difficult.
Really, they don’t even care about the factors themselves, just how much they sum to.
We can define F(n) as the sum of all of the factors of n; so F(6) = 12 and F(12) = 28. Your task
is, given two integers a and b with a ≤ b, to calculate
S =
X
a≤n≤b
F(n).
Input
The input consists of a single line containing space-separated integers a and b (1 ≤ a ≤ b ≤ 1012;
b − a ≤ 106
).
Output
Print S on a single line.
Sample Input and Output
101 101 102
28 28 56
1 10 87
987654456799 987654456799 987654456800
2017 Pacific Northwest Region Programming Contest 9
963761198400 963761198400 5531765944320
5260013877 5260489265 4113430571304040

题意：F(n)是n的因数和，求 $\sum_{n = a}^{b} F (n)$
思路：
方法1：lyr大佬的方法：只枚举每个数的较小因子，另一个通过等差数列求和的方法计算出。复杂度O( $\sqrt{b}$ )

#include<bits/stdc++.h>
using namespace std;
#define maxn 50000+100
#define ll long long

ll a,b,ans;

int main()
{
    cin>>a>>b;
    ll m=sqrt(b+0.5);
    for(ll i=1;i<=m;i++)	//较小因数
    {
        ll l=(a-1)/i+1,r=b/i;  //[l,r]是另一因子的范围
        if(l<i)l=i;   //比如8在2，4时算过，就不算4，2了。
        if(l>r)continue;
        ll t=r-l+1;
        ans+=t*i+(l+r)*t/2;
        if(i*i>=a&&i*i<=b)ans-=i;
    }
    cout<<ans<<endl;
    return 0;
}

方法2：除法分块,，转化为前n个数的因数和，复杂度O( $\sqrt{b}$ )
参考文章：
知识点：https://www.cnblogs.com/SGCollin/p/9630478.html
关于本题：https://blog.csdn.net/qq_39792342/article/details/82780855

#include<bits/stdc++.h>
using namespace std;
#define maxn 50000+100
#define ll long long
#define ull unsigned long long

ll a,b;

ll cal(ll n)
{
    ll ans=0;
    for(ll l=1;l<=n;l++)  //枚举因数
    {
        ll t=n/l;	//前n个数含因数l的数的个数=t
        ll r=n/t;	//[l,r]内的每个数都是t个数的因数，
        ans+=((ull)l+r)*(r-l+1)/2*t; 	//[l,r]作为因数的贡献
        l=r;
    }   
    return ans;
}

int main()
{
   // freopen("input.in","r",stdin);
    cin>>a>>b;
    cout<<cal(b)-cal(a-1)<<endl;
    return 0;
}