挑战58

rosynirvana

很早之前就有人问我，本想直接拿原来的代码来凑数的，结果昨天因为某些原因又写了类似的代码，所以现在写出来吧……

直接穷举的复杂度非常高，我第一次做的时候，先写好直接穷举的代码，然后去查相关的数学知识，代码写完跑出结果后，直接穷举的代码还没跑出结果，所以在这么大的数字的时候，直接穷举就不必考虑了。

题目的关键是要知道相应的数学知识，直角三角形的三边长可以构造出来，具体可以参考
http://zh.wikipedia.org/wiki/%E5%8B%BE%E8%82%A1%E6%95%B0

1. #include <stdio.h>
   
2. int gcd(int, int);
   
3. /* 计算过程中需要判断两个数是否互质，所以一个计算最大公约数的函数是必要的 */
   
4. 
   
5. int count[1500000+1];
   
6. /* 大数组记得要放在静态区 */
   
7. 
   
8. int main()
   
9. {
   
10.   int m, n;
    
11. /* 构造所需的两个变量 */
    
12.   int num = 0;
    
13.   int i;
    
14.   for(m=2; m<=1225; ++m)
    
15. /* sqrt(1500000)上取整，计算到1225绝对够了 */
    
16.     for(n=1; n<m; ++n)
    
17.       if(gcd(m, n) == 1)
    
18.         if(m % 2 == 0 || n % 2 == 0){
    
19.           int a = m*m - n*n;
    
20.           int b = 2*m*n;
    
21.           int c = m*m + n*n;
    
22.           int length = a+b+c;
    
23.           int times = 1;
    
24. 
    
25.           while(times * length <=1500000){
    
26.   /* 所有勾股数都可以用勾股素数来构造 */
    
27.               count[times*length] += 1;
    
28.               times += 1;
    
29.          }
    
30.     }
    
31.     for(i=0; i<=1500000; ++i)
    
32.        if(count[i] == 1)
    
33.          num += 1;
    
34.    /* 计算出来后，扫描一遍表格，把只有一种可能的统计下来 */
    
35.   printf("%d\n", num);
    
36.   return 0;
    
37. }
    
38. 
    
39. /* 计算最大公约数用的函数，个人比较习惯的一种写法，效率应该还可以提高 */
    
40. int gcd(int a, int b)
    
41. {
    
42.   while(a > 0 && b > 0)
    
43.     if(a > b)
    
44.       a %= b;
    
45.     else
    
46.       b %= a;
    
47. 
    
48.   return a > b ? a : b;
    
49. }

复制代码

     

rosynirvana

几个注意的要点：
1. 1500000的大数组要放在静态区，不然有可能把函数栈爆掉
（动态分配也可以，不过这么一小段代码放在静态区就可以了）

2. 计算勾股素数，然后再乘以整数倍，这样可以保证求得的三边长不会重复
如果直接用m, n构造，会出现重复情况的

3. 构造勾股素数的条件在此再写一遍：

a = m*m - n*n;
b = 2*m*n;
c = m*m + n*n;
三边长满足这样的约束关系

其中
m > n;
m % 2 == 0 || n % 2 == 0 (m, n至少有一个是偶数)
gcd(m, n) == 1(m和n互质)

rosynirvana

MoreHail 发表于 2014-7-29 19:31
这个、我就是直接穷举的。。。{:soso__51be3e80bf36fd0f-84cb9798c2b54967-da186aed5a4735fc1066ec7649be28 ...

穷举没意义

rosynirvana

MoreHail 发表于 2014-7-29 19:50
是啊，跑了5、6个小时，都没结果。代码里边，count[1500000+1]是数组么？静态区是什么？怎么放入静态区？

放在所有函数外面定义