HDU_1299 Diophantus of Alexandria
整数分解:
任何一个正整数都可以表示成素数的x次方之积,所以本题就被转化成了求n ^2的素因子个数;
先把n分解得到 n = p1^e1 * p2^e2 * ......*pr^er 其中p是< n 的素数那么n 的素因子个数 k = (e1 + 1) * (e2 + 1) * (e3 + 1)*......
所以:n ^2的素因子数是 (2*e1+1) * (2*e2+1)* (2*e3+1)......
这个题还要注意一点就是当n是素数的时候,很显然 k *= 3,这样做得到的结果是题目要求的2倍
#include <stdio.h>
#include <math.h>
#define max 50000
int num[max], prim[max];
int main()
{
int t, n, i, j, cnt, a, m, pim;
m = 0;
for (i = 1; i < max; ++ i)
{
num[i] = 1;
}
for (i = 2; i < max; ++ i) //筛素数
{
if (num[i])
{
prim[m++] = i;
for (j = i+i; j < max; j += i)
{
num[j] = 0;
}
}
}
scanf("%d", &t);
for (i = 1; i <= t; ++ i)
{
scanf("%d", &n);
cnt = 1;
for (j = 0; j < m; ++ j)
{
pim = (int) sqrt(n*1.0) + 1;
if (prim[j] > pim)
{
break;
}
a = 0;
while (n % prim[j] == 0)
{
a ++;
n /= prim[j];
}
cnt *= (1 + 2 * a);
}
if (n > 1) //当n是素数的时候
{
cnt *= 3;
}
printf("Scenario #%d:\n", i);
printf("%d\n", (cnt+1)/2);
printf("\n");
}
return 0;
}
推荐.NET配套的通用数据层ORM框架:CYQ.Data 通用数据层框架