七夕节---hdu1215(打表求因子和)

时间:2023-12-30 22:27:26

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1215

给你一个数n(1<=n<=50w)求n的所有因子和, 由于n的范围比较大,所以要采用打表的方式,这是第二次看到这道题了,但是还没能够一次写出来。。。

#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <queue>
using namespace std; #define N 501000
#define PI (4*atan(1))
#define met(a, b) memset(a, b, sizeof(a)) typedef long long LL; int sum[N] = {0}; void Init()
{
for(int i=1; i<N; i++)
sum[i] = 1;///1是所有数的因子; for(int i=2; i*i<N; i++)
{
for(int j=i+1; i*j<N; j++)
sum[i*j] += i+j;///i和j一定是i*j的因子;
sum[i*i] += i;
}
} int main()
{
int T, n; Init(); scanf("%d", &T); while(T--)
{
scanf("%d", &n);
printf("%d\n", sum[n]);
}
return 0;
}