在群里看到這樣一個問題：

解法如下：

1 #include <stdio.h> 2 3 #define MAX 500000 4 unsigned g_array[MAX + 1] = {0}; 5 6 #define EVEN(x) (((x)&1)==0) 7 #define ODD(x) (((x)&1)==1) 8 9 //判斷兩個數字是否互質的標準算法 10 unsigned __int64 gcd(unsigned __int64 a, unsigned __int64 b) /* Non-recursive version */ 11 { 12 unsigned __int64 ret=1; 13 unsigned __int64 t =0; 14 L: 15 if(a==b || b==0 ) return ret*a; 16 if( b==1 ) return ret; 17 if( a<b) { 18 t = a; 19 a = b; 20 b = t; 21 goto L; 22 } 23 24 if( EVEN(a) ) { 25 a >>= 1; 26 if( EVEN(b) ) { /* 2*gcd(a>>1, b>>1) */ 27 b >>= 1; 28 ret <<= 1; 29 } /* gcd(a>>1, b) */ 30 else {} 31 } 32 else { 33 if( ODD(b) ) { /* gcd( (a-b)/2, b) */ 34 a -= b; 35 a >>= 1; 36 } 37 else { /* gcd(a, b>>1) */ 38 b >>=1; 39 } 40 } 41 goto L; 42 } 43 44 //填充全局數組內容 45 void GetArray() 46 { 47 unsigned __int64 x; 48 unsigned __int64 y; 49 unsigned __int64 a; //直角邊長度 50 unsigned __int64 b; //另一條直角邊長度 51 unsigned __int64 c; //斜邊長度 52 unsigned __int64 t; //三邊總長度 53 54 for (x = 1; ; x += 1) 55 { 56 //令y的值為最小(為x+1)，用勾股數公式求出三邊長度 57 a = x * (x + 1) * 2; 58 b = (x + 1) * (x + 1) - x * x; 59 c = (x + 1) * (x + 1) + x * x; 60 61 //判斷是否可以提前結束循環 62 if (a + b + c > MAX) 63 { 64 break; 65 } 66 67 //枚舉y，總長度大于MAX時跳出循環 68 for (y = x + 1; y * (x + y) * 2 <= MAX; y += 1) 69 { 70 //用勾股數公式求出三邊長度 71 a = y * x * 2; 72 b = y * y - x * x; 73 c = y * y + x * x; 74 75 //保證三邊互質 76 if (gcd(gcd(a, b), c) == 1) 77 { 78 t = a + b + c; 79 80 //標識所有此總長度的倍數的地方拆分方案數加一 81 while (t <= MAX) 82 { 83 g_array[t] += 1; 84 t += (a + b + c); 85 } 86 } 87 } 88 } 89 } 90 91 int main() 92 { 93 //獲取所有數字的解法數 94 GetArray(); 95 96 //求出其中解法數為一的個數 97 int nCount = 0; 98 for (int n = 0; n <= MAX; n += 1) 99 { 100 if (g_array[n] == 1) 101 { 102 nCount += 1; 103 } 104 } 105 106 printf("%d\n", nCount); 107 108 return 0; 109 } 答案是54446種

轉載于:https://www.cnblogs.com/Shilyx/archive/2013/04/23/3038712.html

總結

以上是生活随笔為你收集整理的将整数拆分为勾股数的问题解决的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。