题意：已知n,求满足条件（x<y<z<n,x^2+y^2=z^2，且x,y,z的最大公约数为1）的数对。

        解题思路：x=a^2-b^2,y=2ab,z=a^2+b^2，根据这一公式，暴力枚举a,b即可。

        下面给出网上大神的证明：

下面给出一位大神的证明：

[解题方法]  
 该题可以归结为数论问题。  
  
 若是用穷举法生成 1000000 以内所有的勾股数，会超时，故需要考虑其他方法。如果方程有一个通解，那  
 么根据通解生成 x，y，z，肯定方便得多，有没有这样的通解公式呢，答案是肯定的，推导如下：  
  
 本题的要求是当 x，y，z ∈ N，给定一个数 n，找出所有的 x，y，z ≤ n，使得 x2 + y2 = z2 成立。  
  
 先假定 x，y，z 互质，若不互质，则可设 x = w * x0，y = w * y0，z = w * z0，将其转化为互  
 质的情形后讨论。由于 x，y，z 互质，故 x，y 中至少有一个是奇数。下面用反证法证明 x 和 y 中有  
 且只有一个奇数。假定 x，y 都为奇数，设：  
  
    x = 2 * a + 1  
    y = 2 * b + 1  
    x2 + y2 = (2 * a + 1)2 + (2 * b + 1)2 = 4(a2 + b2 + a + b) + 2 = z2  
  
 则 z2 是偶数，若 z2 为偶数，则 z 必为偶数，那么 z2 必能被 4 整除，与上式矛盾，因此 x，y 中  
 只有一个奇数。  
  
 假设 x 为奇数，y 为偶数，由于奇数的平方是奇数，偶数的平方是偶数，和 z2 必为奇数，则 z 为奇数。  
 那么 z + x 和 z - x 都是偶数，不妨设 z + x = 2u，z - x = 2v（这是费马提到的一种方法），  
 解得：  
  
    z = u + v  
    x = u - v  
  
 而且由于 x，y，z 互质，则 u，v 也必定互质，若不互质，则可设 u = w * u0，v = w * v0，则  
 z 和 x 有大于 1 的公约数 w，与前提条件矛盾。给原方程两边同除以 4 得：  
  
 x2 / 4 + y2 / 4 = z2 / 4  
  
 然后移项: (y / 2)2 = (z / 2)2 - (x / 2)2  
  
 右边是个平方差公式：  
  
 (z / 2)2 - (x / 2)2 = (z + x) / 2 * (z - x) / 2  
  
 然后把刚才的 u，v 代入上式：  
  
 (z + x) / 2 * (z - x) / 2 = (2 u / 2) * (2 v / 2) = u * v  
  
 也就是说 (y / 2)2 = u * v，说明 u * v 是一个平方数，又因为 u，v 互质，所以 u 和 v 本身  
 都是平方数（为什么？a 和 b 互质，a * b 为完全平方数，设 a * b = u2，则由于(a，b) = 1，  
 所以 a = a * (a，b) = (a2，a * b) = (a2，u2) = (a，u)2，同理 b = (b，u)2）。  
  
 那么，设 u = a2，v = b2，则 a，b 同样也是一奇一偶，互质的两个数（为什么？因为 u 和 v 互质，  
 则必有一个奇数，又由于 y 为偶数，则 u 和 v 不能同为奇数，故必是一奇一偶。由于奇数的平方是奇数，  
 偶数的平方是偶数，则 a 和 b 也是一奇一偶，若 a 和 b 不互质，可推出 u 和 v 不互质，矛盾）。  
  
 从刚才的 (y / 2)2 = u * v，代入 a，b 解出 (y / 2)2 = a2 * b2，y / 2 = a * b，y =   
 2 * a * b。y 解出，将 a，b 代入 x，z 得：  
  
 x = u - v = a2 - b2  
 z = u + v = a2 + b2  
  
 综上所述，可得到下式：  
  
 x = a2 - b2， y = 2 * a * b， z = a2 + b2，(a 与 b 互质，a > b，且一奇一偶)。  
  
 题目要求统计 (x，y，z) 三元组的数量时只统计 x，y 和 z 两两互质的的情况，这个问题用上面的  
 算法就可以解决了。但对于统计 p 的数量，题目并不限定三元组是两两互质的。上式不能生成所有的勾股数。  
 但所有非两两互质的 x0，y0，z0 都可由一组互质的 x，y，z 乘以系数得到。  

UVA 106 求勾股数