这题开始也不知道做,是看了别人的才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
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <stdio.h>
3
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <stdlib.h>
4
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <math.h>
5
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
# define MAXSIZE 40000
6
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
7
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int prime[MAXSIZE];
8
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int primeElem[MAXSIZE];
9
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int cn; //0 -- n内素数的个数
10
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
11
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void is_prime ( )
12
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
![](http://www.cppblog.com/Images/dot.gif)
{
13
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for (int i = 2; i < MAXSIZE; i ++)
14
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![](http://www.cppblog.com/Images/dot.gif)
{
15
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( !prime [i] )
16
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![](http://www.cppblog.com/Images/dot.gif)
{
17
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for (int j = 2 * i; j < MAXSIZE; j += i)
18
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![](http://www.cppblog.com/Images/dot.gif)
{
19
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
prime [j] = 1;
20
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif)
}
21
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
//把 0 -- n 内的素数存到数组中
22
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
primeElem[cn ++] = i;
23
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif)
}
24
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif)
}
25
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockEnd.gif)
}
26
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
27
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main ()
28
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
![](http://www.cppblog.com/Images/dot.gif)
{
29
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int m, n;
30
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
is_prime( );
31
32
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while ( scanf ("%d", &m) != EOF )
33
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![](http://www.cppblog.com/Images/dot.gif)
{
34
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( int i = 0; i < m; i ++)
35
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![](http://www.cppblog.com/Images/dot.gif)
{
36
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
scanf ("%d", &n);
37
38
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
//找到 n 以内的 素因子
39
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int product = 1;
40
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int flag = 0;
41
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( int j = 0; j < cn; j ++)
42
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![](http://www.cppblog.com/Images/dot.gif)
{
43
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
flag = (int) sqrt (n * 1.0) + 1; //n 的 方根
44
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( primeElem[j] > flag ) //p1、p2、p3 这些素数要 < n
45
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
break;
46
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int e = 0;
47
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while ( n % primeElem[j] == 0 )
48
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
![](http://www.cppblog.com/Images/dot.gif)
{
49
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
e ++;
50
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
n /= primeElem[j];
51
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif)
}
52
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
product *= ( 1 + 2 * e);
53
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif)
}
54
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( n > 1 )
55
product *= 3; //这步要注意,最后有可能剩下的n本身就是原来n的素因子 ????
56
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf ("Scenario #%d:\n", i+1);
57
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf ("%d\n", ( product + 1 )/2 );
58
59
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf ("\n");
60
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif)
}
61
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif)
}
62
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
//system ("pause");
63
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
64
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockEnd.gif)
}
65
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted on 2010-08-05 15:18
雪黛依梦 阅读(1345)
评论(0) 编辑 收藏 引用 所属分类:
数论