UVA106 - Fermat vs. Pythagoras（素勾股数） 题目链接 题目大意:给你一个数n，勾股数三元组（x,y,z)的定义：满足x < y < z, x^2 + y^2 = z^2.现在问这里里面有多少个三元组是素勾股数即满足x，y， z两两互质。并且判断剩下的1-n的数有多少是没有出现在勾股数三元组中。 解题思路：先找出所有的素勾股数(x, y, z) ,那么便可

这道题暴力果断的不行啊， n会到达10^2,如果暴力的话，复杂度怎么也得O(n*n). 所以我们压根就不能对a,b,c中的任何数暴力， 但这里有个公式，我也是做了这道题才知道的。 (r*r-s*s)^2+(2*r*s)^2 = (r*r+s*s)^2; 我们只要枚举r和s即可。 效率大大提高了， 下面给出一位大神的证明： [解题方法]    该题可以归结为数论问题。      若