P2424 约数和 题目提供者曹彦臣 难度 普及+/提高 题目背景 Smart最近沉迷于对约数的研究中。 题目描述 对于一个数X，函数f(X)表示X所有约数的和。例如：f(6)=1+2+3+6=12。对于一个X，Smart可以很快的算出f(X)。现在的问题是，给定两个正整数X,Y(X< Y)，Smart希望尽快地算出f(X)+f(X+1)+……+f(Y)的值，你能帮助Smart算出这个值吗？ 输入输出格式 输入格式： 输入文件仅一行，两个正整数X和Y（X< Y），表示需要计算f(X)+f(X+1)+……+f(Y)。 输出格式： 输出只有一行，为f(X)+f(X+1)+……+f(Y)的值。 输入输出样例 输入样例#1： 2 4 输出样例#1： 14 输入样例#2： 123 321 输出样例#2： 72543 说明 对于20%的数据有1≤X＜Y≤105。 对于60%的数据有1≤X＜Y≤1*107。 对于100%的数据有1≤X＜Y≤2*109。
/* 暴力线性递推. */ #include<iostream> #define LL long long using 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 long using 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*(i+j)*(j-i+1)/2; i=j+1; } return tot; } int main() { cin>>x>>y; cout<<slove(y)-slove(x-1); return 0; }