数论经典问题：构造本原勾股数组（PPT）：a^2+b^2=c^2 ， 其中a，b，c两两互质
题意：给你一个n，让你找出一些勾股数组，a^2+b^2=c^2 ， 需要满足a<b<c<=n 。 对于每个case题目首先需要你输出这些勾股数组中PPT的个数，然后再输出一个数字，这个数字是n-所有勾股数组用掉的数字个数
例如：
10
3,4,5 是唯一一组PPT解，所以第一个输出的数字是1
而另外的勾股数组包括 6 8 10 。 那么一共用掉的数字有3,4,5,6,7,8，那么没有用到的数字有4个，所以第二个数字输出4
————————————————————————————————
题意说完了就说怎么解：这个是一个很经典的初等数论问题，在数论概论中第一个问题就是这个问题
勾股数组的个数是无限个，一般的勾股数组并没有太大的研究价值，但是本原勾股数组（PPT）则有，PPT满足a,b,c两两互质，其他的勾股数组都是通过PPT不断翻倍得到的，所以研究本原勾股数组的本质和性质很重要
看了那一章然后自己在哦纸上写了一次证明，基本上算是搞懂了，但是不想再在电脑上打一遍，就简单说一下证明的过程
1.证明a和b必定一奇一偶，并可以推导出c一定是奇数 。 证明后我们约定a是奇数，b是偶数，c为奇数，但a和b的大小不能确定
2.a^2+b^2=c^2 ---> a^2=c^2-b^2=(c+b)*(c-b) , 那么可知（c+b）和（c-b）都是奇数
然后证明 （c+b）与（c-b）互质，并且两者都是平方数
3.因为（c+b）与（c-b）都是平方数，则
（c+b）=s^2 ; (c-b)=t^2 ; ，满足s>t>=1
很容易证明s与t都是奇数，并且两者互质
4.用s和t来表示a，b，c
a=s*t
b=(s*s-t*t)/2
c=(s*s+t*t)/2
有最后得到的这3条式子，我们知道了构建PPT的方法，就是不断枚举两个奇数s和t，只要s和t互质，就可以通过这3条式子得到a，b，c，它们就是一组PPT。得到一组PPT后就不断翻倍得到其他的勾股数组
最后回到题目，要满足a<b<c<=n , 所以枚举s和t的时候可以缩小范围，否则会超时，具体实现看代码，注释写得很详细了
#include <cstdio> #include <cmath> #include <cstring> #define N 1000010 bool used[N]; long long gcd(long long a , long long b) { return b==0 ? a: gcd(b,a%b); } int main() { long long n,a,b,c; long long count1,count2; while(scanf("%lld",&n)!=EOF) { count1=count2=0; memset(used,0,sizeof(used)); long long m=(long long)sqrt(n+0.5); for(long long t=1; t<=m; t+=2) for(long long s=t+2; s*t<=n; s+=2) if(gcd(s,t)==1) //s>t>=1且s与t互质 { a=s*t; //奇数 b=(s*s-t*t)/2; //偶数 c=(s*s+t*t)/2; //奇数 if(c<=n) //在n范围内的PPT { count1++; //printf("本原勾股数组：%lld %lld %lld\n",a,b,c); if(!used[a]) { count2++; used[a]=1; } if(!used[b]) { count2++; used[b]=1; } if(!used[c]) { count2++; used[c]=1; } for(int j=2; c*j<=n; j++) //j是倍数 { if(!used[a*j]) { count2++; used[a*j]=1; } if(!used[b*j]) { count2++; used[b*j]=1; } if(!used[c*j]) { count2++; used[c*j]=1; } } } } printf("%lld %lld\n",count1,n-count2); } return 0; }