Problem Description

程序设计课的老师给Coral布置了一道题:用T(n)表示所有能整除n的正整数之和,对于给定的数字n,记S(n)=T(1)+T(2)+…+ T(n)。你的任务就是帮助Coral求出S(n)。

FZU 1591 Coral的烦恼-LMLPHP Input

本题有多组输入数据,你必须处理到EOF为止。

每组数据输入仅一行一个整数n (1<=n<2)。

FZU 1591 Coral的烦恼-LMLPHP 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=;
__int64 l,r;
while(scanf("%d",&n)!=EOF){
ans=;
for(i=;i*i<=n;i++){
l=n/(i+)+,r=n/i;
if(l>i)
ans+=(l+r)*(r-l+)/*i;
ans+=(n/i)*i;
}
printf("%I64d\n",ans);
}
return ;
}
04-28 18:19