Divisor Summation

Divisor Summation

时间： 1ms        内存：64M

描述：

Give a natural number n (1 <= n <= 500000), please tell the summation of all its proper divisors. Definition: A proper divisor of a natural number is the divisor that is strictly less than the number. e.g. number 20 has 5 proper divisors: 1, 2, 4, 5, 10, and the divisor summation is: 1 + 2 + 4 + 5 + 10 = 22.

输入：

An integer stating the number of test cases, and that many lines follow each containing one integer between 1 and 500000.

输出：

One integer each line: the divisor summation of the integer given respectively.

示例输入：

3
2
10
20

示例输出：

1
8
22

提示：

参考答案（内存最优[1496]）：

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int main()
{
	int T;
	int n;
	cin>>T;
	while(T--)
	{
		scanf("%d",&n);
		if(n==1)
		{
			cout<<0<<endl;
			continue;
		}
		int sum=1;
		for(int i=2;i<=sqrt(n);i++)
		{
			if(n%i==0)
			{
				if(n/i==i)
				sum+=i;
				else sum+=i+n/i;
			}
		}
		printf("%d\n",sum);
	}
	return 0;
}

参考答案（时间最优[28]）：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=500000+10;
int a[maxn];
void table()
{
    int i,j;
    int m=sqrt(500000);

    for(i=2; i<=500000; i++)
        a[i]=1;
    a[1]=0;
    for(i=2; i<=m; i++)
    {
        a[i*i]+=i;
        for(j=i+1; j<=(500000/i); j++)
        {
            a[i*j]+=i+j;
        }
    }
}
int main()
{
    int t,n;
    table();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        printf("%d\n",a[n]);
    }
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。