题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1215
解题思路:
这道题要求的就是一个整数的因子之和。
但是这道题在杭电数据比较弱,各种方法都能过。暴力都能过,但是在我们OJ,只能使用优化的代码。因为数据是1-500000,暴力的话,估计得跑个几十秒。
下面说下这道题的优化解法:
1.素数打表,这个就不说了,基本功。
2.接下来就是这个问题的关键:素分解。不会的可以移步这篇文章:http://wenku.baidu.com/view/e55ca209ba1aa8114431d98a.html
代码如下:
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
#define CLR(arr, what) memset(arr, what, sizeof(arr))
const int N = 500002;
int prim[N];
bool visit[N];
void fast_prim() //素数打表
{
memset(visit, true, sizeof(visit));
int limit = (int)sqrt(N * 1.0);
for(int i = 2; i < limit; ++i)
if(visit[i])
for(int j = i * i; j < N; j += i)
visit[j] = false;
for(int i = 2, j = 0; i < 10000; ++i)
if(visit[i])
prim[j++] = i;
}
int prim_reduce(int n) //整数素分解
{
int limit, num, sum, total = 1, temp = n;
limit = sqrt(N * 1.0);
for(int i = 0; prim[i] * prim[i] <= n; ++i)
{
num = sum = 1;
if(n == 1)
break;
while(n % prim[i] == 0)
{
num *= prim[i];
n /= prim[i];
sum += num;
}
total *= sum;
}
if(n != 1)
total *= (n + 1);
return total - temp;
}
int main()
{
fast_prim();
int ncase;
int num;
scanf("%d", &ncase);
while(ncase--)
{
scanf("%d", &num);
if(num == 1)
{
printf("0\n");
continue;
}
else if(visit[num])
{
printf("1\n");
continue;
}
else
printf("%d\n", prim_reduce(num));
}
return 0;
}
第二种方法:
在于打表的过程不同,第一种方法是解决这种问题的通法,但这道题我们可以用另一种打表方面,a[i]代表的就是这个因子之和,这样,我们就可以一次打表,O(1)输出。
代码如下:
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
#define CLR(arr, what) memset(arr, what, sizeof(arr))
const int N = 500002;
const int M = 250000;
int a[N] = {0, 0};
void fash()
{
for(int i = 2; i < N; ++i) //因子初始化为1
a[i] = 1;
for(int i = 2; i <= M; ++i) //一半即可
for(int j = 2 * i; j < N; j += i)
a[j] += i;
}
int main()
{
fash();
int ncase;
scanf("%d", &ncase);
while(ncase--)
{
int num;
scanf("%d", &num);
printf("%d\n", a[num]);
}
return 0;
}