是個經典問題了，求滿足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！