Problem C — limit 1 second Fear Factoring 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= ? F(n). a≤n≤b 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
推荐阅读：https://www.luogu.com.cn/blog/KingofNight/post-shuo-lun-zheng-shuo-fen-kuai-ji-yang-xi-zheng-ming 题意： a~b直接所有数的约数和。 我们要求得是 ∑[n/i] X i。但是n太大了，枚举i不可能。注意到，每一个连续块的n/i数目是相同的，只要我们找到这个数目相同块的左边界和右边界，就可以一块一块的求了。
左边界就是上一次的边界+1，右边界呢？ 假设有 n / a = b n / a = b n/a=b 假设 r = n / ( n / a ) = n / b r = n / (n / a) = n / b r=n/(n/a)=n/b 如果 r ∗ b = x − k r*b = x -k r∗b=x−k,那么 k < b k<b k<b 那么有结论 n / r = b n / r = b n/r=b 证明： r ∗ b = n − k , k < r r*b=n-k,k<r r∗b=n−k,k<r 那么 r = ( n − k ) / b r=(n-k)/b r=(n−k)/b 那么 n / r = b n / ( n − k ) ≥ b n/r=bn/(n-k)≥b n/r=bn/(n−k)≥b
假设 n / r ≥ b + 1 n/r≥b+1 n/r≥b+1 那么 n ≥ r ∗ b + r n≥r*b+r n≥r∗b+r 那么 r ∗ b ≤ n − r r*b≤n-r r∗b≤n−r 又因为 r ∗ b = n − k , k < r r*b=n-k,k<r r∗b=n−k,k<r 得到 k ≥ r k≥r k≥r，与已知矛盾，故不成立
所以 b ≤ n / r < b + 1 b≤n/r<b+1 b≤n/r<b+1 所以 n / r = b n/r=b n/r=b
又可以有结论 r 是最大的使得x/a=b的a。 证明： 假设 r 不是最大的使得x/a=b的a, 那么 x / ( r + 1 ) = b x / (r+1) = b x/(r+1)=b。 那么 ( r + 1 ) ∗ b = x − g , g < r , b (r+1)*b = x - g, g < r,b (r+1)∗b=x−g,g<r,b 那么 r ∗ b + b = x − g r*b+b=x-g r∗b+b=x−g,即 x − k + b = x − g x-k+b=x-g x−k+b=x−g 那么 k − g = b k-g=b k−g=b 与已知矛盾，故r是足底啊的使得x/a=b的a.
所以b对应的是n / a = b的最大的a。那么右边界就是 n / (n / l) + 1。
#include <cstdio> using namespace std; typedef unsigned long long ll; ll cal(ll n) { ll j = 0,ans = 0; for(ll i = 1;i <= n;i = j + 1) { j = n / (n / i);//n/i为约数i的数目，n / (n/i)代表着约数数目为n/i的右边界。 ans += (i + j) * (j - i + 1) * (n / i) / 2; } return ans; } int main() { ll a,b;scanf("%lld%lld",&a,&b); printf("%lld\n",cal(b) - cal(a - 1)); return 0; }