题目背景
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。
/* 对于这个题目，肯定要用查分，一个朴素的算法是枚举所有因数，然后计算因数在1~x的约数中出现的次数，如果该约数为i，那么出现的次数就是x/i次，这样问题就转换为了求Σi*(x/i)，但是O(n)超时。 我们不难发现对于所有的x/i，可能有连续一段区间是相同的，而且不同的x/i只有O(sqrt(x))个，那么我们就可以计算出某个x/i出现的区间，求和就行啦！ */ #include<cstdio> #include<iostream> #define lon long long using namespace std; lon work(lon x){ lon l=1,r,v=0; while(1){ r=x/(x/l); v+=(x/l)*((l+r)*(r-l+1)/2); l=r+1; if(l>x) break; } return v; } int main(){ lon x,y;cin>>x>>y; cout<<work(y)-work(x-1); return 0; }