是个经典问题了，求满足a ^ 2 + b ^ 2 = c ^ 2且a、b、c两两互质的三元组个数，其中a、b、c都小于等于n，同时还要求出n以内不属于三元组（不必互质）的数的个数，其中n <= 1000000。
　　数据范围很大，单纯的n ^ 2的枚举肯定是不行的。我发现互质的三元组不多，想找一个办法求出互质的，然后筛出其他的三元组（乘以倍数），但是仍然想不出怎样很快找到互质的三元组。到网上查了一下，找到了一个很好的网站（http://xserve.math.nctu.edu.tw/people/cpai/carnival/fraction/05.htm）讲解这个问题。
　　首先只需找到互质的a和b就可以了，其余的可以通过乘以一定的倍数得到。首先a和b必须不能都是奇数，否则的话，不妨设a = 2p + 1, b = 2q + 1, c = 2r。带入a ^ 2 + b ^ 2 = c ^ 2有：2 * (r ^ 2 - p ^ 2 - q ^ 2 - p - q) = 1，出现了矛盾。这样必然a和b一奇一偶，设a是偶数。恒等变换一下：（这里是x ^ 2 + y ^ 2 = z ^ 2，x是偶数）

　　令u = (z - y) / 2，v = (z + y) / 2。因为y、z互质，那么u、v互质。如果不互质，有v = ku，变换后得到：z / y = (k + 1) / (k - 1)。因为z和y互质，这样这个等式的解只能是z = k + 1且y = k - 1。这样的话u = 1。可以理解为这也是互质的特殊情况(gcd = 1)。这样(x / 2) ^ 2 = u * v，u和v没有公共的质因数，因此必然u和v都是完全平方数。接下来的事情就比较简单了，令u = m ^ 2，v = n ^ 2，然后利用m和n表示x、y、z有：y = n ^ 2 - m ^ 2，x = 2 * m * n，z = n ^ 2 + m ^ 2。这样题目中数据范围1000000，而枚举m和n的范围最大1000，这个复杂度就可以接受了。枚举的时候不用担心出现重复的互质的x与y，因为这里x一定是偶数，如果x和y已经互质，那么y一定是奇数，解是唯一的。
　　很囧的是这个巧妙的方法居然公元前250年就有大牛想到了（丢番图），实在orz！