Problem Description
程序设计课的老师给Coral布置了一道题：用T(n)表示所有能整除n的正整数之和，对于给定的数字n，记S(n)=T(1)+T(2)+…+ T(n)。你的任务就是帮助Coral求出S(n)。
Input
本题有多组输入数据，你必须处理到EOF为止。
每组数据输入仅一行一个整数n (1<=n<231)。
Output
输出一行一个数字S(n)。
有种 O（N）的算法 for(i = 1; i <= N; i++) sum(i*(n/i));
意思就是 枚举每个 因子总共出现的次数乘以该因子 比如 在100 中 2会被计算 50次 3会被计算33次 那么 2*50 + 3*33就是 因子2和因子3在n=100时的总和
但是我们可以将复杂度简化到 sqrt(N)；
对于给定的 N，记 sq = sqrt(N)；
对于 1<= i < sq，计算
sum(i*(n/i))，这样得到了答案的一部分(对于小于 sq 的因子 i 乘以所有可能的个数，再加起来)。
那么 >= sq 的因子 j
呢？
我们可以统计自 j 到 N 的数中，某因子出现 1 次的数（肯定是连续的）的个数，出现 2 次的数（肯定是连续的）的个数，。。。。。。
比如
N = 12；sq = 3；
那么因子 1,2,3 招致的和就是 1* 12 + 2*6 + 3* 4 = 36。
自 4 到 12 ，该因子 出现 1 次的数是 7,8,9,10,11,12；和是 (7+ 12) * 6/2 = 57；
该因子出现 2 次的数是 5,6，和是 (5+6) * 2 = 22；
该因子出现 3 次的数是 4，和是 12。
那么出现 ii 次的数是 (N/(1+ii), N/ii]。
转自 http://218.245.3.161/2011/03/08/5687
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <math.h> #include <stdio.h> #include <string.h> using namespace std; #define maxm 100010 #define maxn 1000110 int main() { int n; int i; __int64 ans=0; __int64 l,r; while(scanf("%d",&n)!=EOF){ ans=0; for(i=1;i*i<=n;i++){ l=n/(i+1)+1,r=n/i; if(l>i) ans+=(l+r)*(r-l+1)/2*i; ans+=(n/i)*i; } printf("%I64d ",ans); } return 0; }