题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4926
题目大意： 定义一个数的所有因子（包括自身也包括1）的和，为这个数 的MLCM。 题目要求的是，给出一个n，1<n<20000001,求出 从2到n的所有数（以下找规律时是算进了1，结果出来后会减掉）的 MLCM的和。
多组输入数据。每组最多有100个。
恕我愚昧，这道题我想了好几次，都没有思路便草草放弃，今天终决心啃下来，没想到A了。
起初先想到是唯一分解定理。求一个数的所有因子和问题，然后O（n）的时间全部累加起来。然而发现算上数据组数 10^9必然是超时结局。
百般无奈之下，百度了一下众位大佬的思路，结果 有一种方法是 类似埃及筛法的暴力打表法，还有一种是用了神奇的因式分解，还有一种是二分......
最后，都没有看懂。
但是有一句话突然让我注意到了一点， （很好奇是怎么发现的）任何一个数 i ，在题意要求的的所有因子里面出现了 n/i 次 。
（再强调。。这里整理思路的时候是加了 1的，后面结果会减掉）
也就是说，第一个样例里面 10， 满足题意的所有因子中
1出现了10次
2出现了5次
3出现了3次
4出现了2次
5出现了2次
6出现了1次
7、8、9、10都只出现了1次
发现从1到10， 出现的次数都是顺序递减的。而接下来的操作只要 把 每个因子 乘以 它出现个数 ，全部加起来 就是题意所求了。
这样求出各个因子的值 并且 相加 ，还是O（n）啊。
对于每个因子从 1 , 2 , 3 , 4 4 , 5 , 6 , 7 , 8 ， ....... ，n 他们的出现次数由大到小递减。
相加过程能不能用数学方法进行跳跃相加呢？ 我认真的思考这个问题，没想出来......
但是跳跃相加！ 在这个 各因子的出现次数 都是顺序递减的 这个序列里，不就可以用二分查找了！
从左边开始 对不同的次数的区间边界进行二分查找，使得查找得到的区间，区间内的所有数的出现的次数都是一样的。 然后对区间里的数字运用求和公式即可。
在查找前，不需要先把每个数字的出现次数预处理出来。可以边查边算。
敲了一下代码 发现 即使是 20000000，出现的不同的次数 ，是8942个。
而 即使 是 log（20000000） 也就是16.12
也就是说，按照题目的最坏的情况，也只需要 二分查找8942次，每次折半查找16次，不会超时。
下面上代码。
#include<iostream> #include <cstdio> #include <cmath> using namespace std; int main() { int l,r,i,j,n,m,value,index; ll ans; while(~scanf("%d",&n)) { if(!n)break; ans=0; //ans计入答案 l=1; //二分查找初始化 r=n; index=1; //计入每一次二分查找的起点 value=n/index; //value为二分查找的目标左区间（最左侧数字的次数） while(1) { if(index>n)break; //左区间超出范围则停止 while(l<=r) //二分查找 最后的r是右区间的位置 {m=(l+r)>>1; if(n/m<value)r=m-1; else l=m+1; } ans+=(ll)(index+r)*(r-index+1)*(n/index)/2; //ans加上区间的各数*出现次数 求和公式一下 注意“强制转换”不可省略！！ index=r+1; //一趟结束，为下一次的二分做 “向右迈进” value=n/index; l=index; r=n; } printf("%lld\n",ans-1); //要减去一个1，上文声明过 } return 0; }
完毕~~（结果和唯一分解定理 没有半分关系~）
