這題開始也不知道做，是看了別人的才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
雪黛依夢 閱讀(1372)
評論(0) 編輯 收藏 引用 所屬分類:
數論