最近好久没有写博客了╮(╯_╰)╭，堆积了一堆题，打cf之前没事做就写一下博客\(≧▽≦)/（主要是因为懒癌晚期(￣△￣；)）
题目：
勾股定理是我们中华名族的骄傲，可惜在很多书上都不是这样命名的。今天我们来算算勾股数，也就是说给定一个正整数N，找出所有小于N的三个正整数a，b，c，满足：a*a+b*b=c*c，且a<=b< c以及a，b，c三者的最大公约数为1。
Input 本问题有多组测试数据，每一组就一行，包含三个正整数N,L,R (1<=N,L,R<=1000000,L<=R, R – L <=100)。
Output 输出对所有满足题目要求勾股数，依次按a，b，c排序后的结果编号在[L,R]区间内的所有勾股数。 输出有两部分，第一部分是满足条件的解的组数M；第二部分是M行的解，解的输出格式请参见Sample Output的格式。 注意输出时有输出格式问题的，即Case:后面有一个空格，case数后面也有一个空格。输出排序请参见Sample Output的排序。
Sample Input 20 1 4 20 2 3
Sample Output 3 Case: 1 a=3,b=4,c=5 Case: 2 a=5,b=12,c=13 Case: 3 a=8,b=15,c=17 2 Case: 1 a=5,b=12,c=13 Case: 2 a=8,b=15,c=17
思路：a*a+b*b=c*c，(x+y)^2=(x-y)^2+4*x*y是不是和这个式子很像，a=x-y,b=sqrt(4*x*y),c=x+y，为了凑成整数，可以变式为a=x^2-y^2,b=2*x*y,c=x^2+y^2，这样子遍历一下x和y就可以找出勾股数了，然后按照题目要求筛选一下。
下面是代码：
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<queue> #include<cmath> #include<algorithm> #define N 1000000 #define LL long long using namespace std; struct point{ LL x,y,z; }gg[N]; int n,l,r; int len; queue<point> q; int cmp(point a,point b) { if(a.x!=b.x) return a.x<b.x; else if(a.y!=b.y) return a.y<b.y; else return a.z<b.z; } LL gcd(LL a,LL b) { if(b!=0) return gcd(b,a%b); else return a; } void init() { len=0; for(LL i=2;i*i<=N;i++) { for(LL j=1;j<i;j++) { if(i*i+j*j>N) continue; gg[len].x=i*i-j*j; gg[len].y=2*i*j; if(gg[len].x>gg[len].y) swap(gg[len].x,gg[len].y); gg[len].z=i*i+j*j; if(gcd(gg[len].x,gcd(gg[len].y,gg[len].z))==1) len++; } } sort(gg,gg+len,cmp); //printf("%d\n",len); } int main() { init(); while(~scanf("%d%d%d",&n,&l,&r)) { int tmp=0,k=1; for(int i=0;i<len;i++) { if(gg[i].z<=n) { q.push(gg[i]); } } printf("%d\n",max(min(r,(int)q.size())-l+1,0)); while(!q.empty()) { point t=q.front(); tmp++; if(tmp>=l&&tmp<=r) { printf("Case: %d a=%lld,b=%lld,c=%lld\n",k++,t.x,t.y,t.z); } q.pop(); } } }