勾股数组
设三元组(a,b,c)满足a^2 + b^2 = c^2的勾股数组，那么是否存在无穷多个勾股数组呢，
答案是肯定的，将三元组乘以d，可以得到新的三元组(da,db,dc) 即(da)^2 + (db)^2 = (dc)^2 --> (a^2+b^2) * d^2 =c^2 * d^2
d的取值是任意的，所以存在多个勾股数组
本源勾股数组
本源勾股数组是一个三元组(a,b,c),其中a,b,c只存在公因数1，且满足a^2 + b^2 = c^2
积累数据：下面的一些本源勾股数组
(3,4,5), (5,12,13) ,(8,15,17),(7,24,25)
(20,21,29),(9,40,41),(12,35,37),(11,60,61)
分析数据：
由这些数据可以推断出可能存在一个结论，即a,b的奇偶性不同，且c总是奇数
证明：如果a,b都是偶数，那么c肯定也是偶数，那么a,b,c存在公因子2，所以三元组不是本源的
如果a,b都是奇数， 那么c必然是偶数。 设a=2*x+1, b=2*y+1,c=2*z将其带入a^2 + b^2 = c^2
得到(2x+1)^2 + (2y+1)^2 = (2z)^2 --> 4x^2+4x+4y^2+4y+2=4z^2 --> 2x^2+2x+2y^2+2y+1=2z^2
式子的左边是一个奇数，而右边是偶数，所以上述假设不成立
所以a,b一个是偶数，一个是奇数，从而c是奇数
怎么快速得到一定范围内的本源勾股数组
(a,b,c)是本源勾股数组， 且a是奇数 ，b是偶数，c是奇数，那么可以进行因式分解，
a^2 = c^2 - b^2 = (c-b)(c+b)
3^2 = (5-4)(5+4) = 1 * 9
15^2 = (17-8)(17+8) = 9 * 25
32^2 = (37-12)(37+12) = 25 * 49
好像c-b与c+b总是平方数，
证明：假设(c-b)%d==0 && (c+b)%d==0, 那么根据模的性质，有(c+b)+(c-b) = 2c, 2c%d==0, 且(c+b)-(c-b)=2b,2b%d==0,
即d整除2b和2c, 因为b和c没有公因数，所以d只能是1或者2， 由(c+b)(c-b)=a^2 也是d的倍数，且a是奇数，所以a^2是奇数，所以d只能取值1
所以(c-b)与(c+b)互素，且(c-b)(c+b)=a^2, 即(c-b)与(c+b)的和是平方数，这种情况只有在(c-b)与(c+b)本身都是平方数的时候才出现
如图：
因为(c-b)与（c+b)互素，所以pi 与qi肯定是不相同的，但是(c-b)(c+b)=a^2， 所以指数ai ,bi肯定是偶数的，所以(c+b) 和 (c-b)本身都是平方数
设c+b=s^2,c-b=t^2, 其中s>t>=1是没有公因数的奇数
解方程得
uva106
给我们一定n，要我们求1->n内有多少个本源勾股数组， 和多少个不属于勾股数组的数字
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
#pragma warning(disable:4996)
typedef long long LL;
const int INF = <<;
/* */
bool vis[ + ];
int ans1[ + ];
int gcd(int a, int b)
{
if (b == )
return a;
return gcd(b, a%b);
}
int main()
{
int s, t, a, b, c;
int cnt = , n;
while (scanf("%d", &n) != EOF)
{
cnt = ;
memset(ans1, , sizeof(ans1));
memset(vis, , sizeof(vis));
int m = sqrt(*n);
for (s = ; s <= m; s += )
{
for (t = ; t < s; t += )
{
if (gcd(s, t) != ) continue;
a = s * t;
b = (s*s - t*t) / ;
c = (s*s + t*t) / ;
if (c>n) break;
if ((LL)a*a + (LL)b*b == (LL)c*c)
{
//printf("%d %d %d\n", a, b, c);
ans1[c]++;
for (int i = a, j = b, k = c; k <= n; i += a, j += b, k += c)
vis[i] = vis[j] = vis[k] = true;
}
else if ((LL)a*a + (LL)b*b < (LL)c*c)
break;
}
} for (int i = ; i <= n; ++i)
{
ans1[i] += ans1[i - ];
if (!vis[i])
cnt++;
}
printf("%d %d\n", ans1[n], cnt);
}
return ;
}