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的因数和,求 n = a b F ( n ) \sum_{n=a}^bF(n) n=abF(n)
思路:
方法1:lyr大佬的方法:只枚举每个数的较小因子,另一个通过等差数列求和的方法计算出。复杂度O( b \sqrt{b} 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( b \sqrt{b} 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;
}
全部评论

相关推荐

05-09 12:23
已编辑
华南理工大学 Java
野猪不是猪🐗:给他装的,双九+有实习的能看的上这种厂我直接吃⑨✌们拿它练练面试愣是给他整出幻觉了
点赞 评论 收藏
分享
吐泡泡的咸鱼:我也工作了几年了,也陆陆续续面试过不少人,就简历来说,第一眼学历不太够,你只能靠你的实习或者论文或者项目经历,然后你没有论文,没有含金量高的比赛和奖项,只能看实习和项目,实习来说,你写的实习经历完全不清楚你想找什么工作?行研?数据分析?且写的太少了,再看项目,这些项目先不说上过大学读过研究生的都知道很水,然后对你想找的岗位有什么帮助呢?项目和实习也完全不匹配啊,你好像在努力将你所有的经历都放在简历里想表现你的优秀,但是对于你想找的岗位来说,有什么用呢?最后只能获得岗位不匹配的评价。所以你需要明白你想要找的岗位要求是什么,是做什么的,比如产品经理,然后再看你的经历里有什么匹配的上这个岗位,或者对这个岗位以及这个岗位所在的公司有价值,再写到你的简历上
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务