C - Fear Factoring Gym - 101615C（求约数和，除法分块）

本文主要是介绍C - Fear Factoring Gym - 101615C（求约数和，除法分块），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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$
假设$r=n/(n/a)=n/b$
如果$r\ast b=x-k$,那么$k<b$
那么有结论 $n/r=b$
证明：
$r\ast b=n-k,k<r$
那么$r=(n-k)/b$
那么$n/r=bn/(n-k)\ge b$

假设 $n/r\ge b+1$
那么$n\ge r\ast b+r$
那么$r\ast b\le n-r$
又因为$r\ast b=n-k,k<r$
得到$k\ge r$，与已知矛盾，故不成立

所以$b\le n/r<b+1$
所以$n/r=b$

又可以有结论 r 是最大的使得x/a=b的a。
证明： 假设 r 不是最大的使得x/a=b的a,
那么 $x/(r+1)=b$。
那么$(r+1)\ast b=x-g,g<r,b$
那么 $r\ast b+b=x-g$,即 $x-k+b=x-g$
那么$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;
}

这篇关于C - Fear Factoring Gym - 101615C（求约数和，除法分块）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---