勾股数组及其应用uva106

勾股数组

设三元组(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)本身都是平方数的时候才出现

如图:

  勾股数组及其应用uva106

因为(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

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 ;
}
上一篇:streamsets 3.5 的一些新功能


下一篇:LaTeX中的数学公式