洛谷 P2424 约数和

2019-11-14 09:57:23

字体：大中小

来源：转载

供稿：网友

P2424 约数和题目提供者曹彦臣 难度 普及+/提高 题目背景 Smart最近沉迷于对约数的研究中。题目描述对于一个数X，函数f(X)表示X所有约数的和。例如：f(6)=1+2+3+6=12。对于一个X，Smart可以很快的算出f(X)。现在的问题是，给定两个正整数X,Y(X

/*暴力线性递推.*/#include<iostream>#define LL long longusing namespace std;LL ans,x,y;int main(){ cin>>x>>y; for(int i=1;i<=x-1;i++) ans-=(x-1)/i*i; for(int i=1;i<=y;i++) ans+=y/i*i; cout<<ans; return 0;}/*这题正解蛮神的.暴力的话就nsqrt(n)对每个数进行质因数分解.然后我们考虑优化.我们知道1-n中i的倍数有[n/i]个.然后我们就可以线性递推了.但是这样依然过不了此题.我们令s[i]=f[1]+f[2]+f[3]+..... =[i/1]*1+[i/2]*2+[i/3*3]+.....然后我们会发现里边有些值是相同的.so 我们可以用等差数列加速.ans=s[y]-s[x-1].复杂度sqrt(n). */#include<iostream>#define LL long longusing namespace std;LL ans,x,y;LL slove(LL n){ LL i=1,tot=0; while(i<=n) { int j=n/(n/i); tot+=n/i*(j-i+1); i=j+1; } return tot;}int main(){ cin>>x>>y; cout<<slove(y)-slove(x-1); return 0;}

上一篇：python生成素数的程序

下一篇：codevs 1231_最优布线问题_最小生成树