整数分解:

  任何一个正整数都可以表示成素数的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;
}

作者: ╰☆惔、煙菋 发表于 2011-04-02 14:42 原文链接

推荐.NET配套的通用数据层ORM框架:CYQ.Data 通用数据层框架
新浪微博粉丝精灵,刷粉丝、刷评论、刷转发、企业商家微博营销必备工具"