这题开始也不知道做，是看了别人的才AC的，感觉数论好高深的。
分析易知：x、y是大于n的；
设y = n + k ( k > = 1),则：x = n 2 / k + n;
所以本题关键是找到使x 为整数的k的个数，
由定理：任何一个正整数都可以表示成两个素数之积，所以本题就被转化成了求n ^2的素因子个数；
n = p1^e1 * p2^e2 * ......*pr^er; 其中p是< n 的素数
那么n 的素因子个数 (e1 + 1) * (e2 + 1) * (e3 + 1)*......
所以：n ^2的素因子数是 (2*e1+1) * (2*e2+1)* (2*e3+1)......
1
//为什么要把范围缩小到n的方根之内呢？？ 2
#include <stdio.h>
3
#include <stdlib.h>
4
#include <math.h>
5
# define MAXSIZE 40000
6
7
int prime[MAXSIZE];
8
int primeElem[MAXSIZE];
9
int cn; //0 -- n内素数的个数
10
11
void is_prime ( )
12
{
13
for (int i = 2; i < MAXSIZE; i ++)
14
{
15
if ( !prime [i] )
16
{
17
for (int j = 2 * i; j < MAXSIZE; j += i)
18
{
19
prime [j] = 1;
20
}
21
//把 0 -- n 内的素数存到数组中
22
primeElem[cn ++] = i;
23
}
24
}
25
}
26
27
int main ()
28
{
29
int m, n;
30
is_prime( );
31
32
while ( scanf ("%d", &m) != EOF )
33
{
34
for ( int i = 0; i < m; i ++)
35
{
36
scanf ("%d", &n);
37
38
//找到 n 以内的 素因子
39
int product = 1;
40
int flag = 0;
41
for ( int j = 0; j < cn; j ++)
42
{
43
flag = (int) sqrt (n * 1.0) + 1; //n 的 方根
44
if ( primeElem[j] > flag ) //p1、p2、p3 这些素数要 < n
45
break;
46
int e = 0;
47
while ( n % primeElem[j] == 0 )
48
{
49
e ++;
50
n /= primeElem[j];
51
}
52
product *= ( 1 + 2 * e);
53
}
54
if ( n > 1 )
55
product *= 3; //这步要注意，最后有可能剩下的n本身就是原来n的素因子 ????
56
printf ("Scenario #%d:\n", i+1);
57
printf ("%d\n", ( product + 1 )/2 );
58
59
printf ("\n");
60
}
61
}
62
//system ("pause");
63
return 0;
64
}
65
posted on 2010-08-05 15:18
雪黛依梦 阅读(1354)
评论(0) 编辑 收藏 引用 所属分类:
数论