本文主要是介绍2862--勾股定理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
勾股定理
Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^
题目描述
给N个数，判断这N个数中存在多少组勾股数（勾股数：存在三个数满足a*a + b*b = c*c）。
输入
第一行输入一个数T(1<=T<=50)，表示有T组数据。
每组数据输入一个N(1<=N<=1000)。
接下来N个数ai(1<=ai<=10^9)。
输出
每组数据输出一行，表示有多少组勾股数。
示例输入
3 4 4 3 5 3 4 6 7 8 10 5 6 7 8 9 5
示例输出
2 1 0
提示
来源
枚举两边，对第三遍做二分查找
示例程序
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
long long int p[2000] ;
int num[2000] ;
int main()
{
int t , i , j , n , l , ans ;
long long int k ;
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
for(i = 0 ; i < n ; i++)
{
scanf("%lld", &p[i]);
p[i] *= p[i] ;
}
sort(p,p+n);
/*for(i = 0 ; i < n ; i++)
printf("%lld ", p[i]);
printf("\n");*/
memset(num,0,sizeof(num));
k = -1 ;
l = 0 ;
for(i = 0 ; i < n ; i++)
{
if(p[i] != k)
{
num[i] = 1 ;
l = i ;
k = p[i] ;
}
else
num[l]++ ;
}
k = -1 ;
for(i = 0 ; i < n ; i++)
if(num[i] == 0)
num[i] = k ;
else
k = num[i] ;
/*for(i = 0 ; i < n ; i++)
printf("%d ", num[i]);
printf("\n");*/
ans = 0 ;
for(i = 0 ; i < n ; i++)
{
for(j = i+1 ; j < n ; j++)
{
k = p[i]+ p[j] ;
int low = 0 , mid , high = n-1 ;
while(low <= high)
{
mid = (low + high) / 2 ;
if( p[mid] == k )
break;
else if( p[mid] < k )
low = mid + 1 ;
else
high = mid - 1 ;
}
if(p[mid] == k)
ans++ ;
}
}
printf("%d\n", ans);
}
}
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
long long int p[2000] ;
int num[2000] ;
int main()
{
int t , i , j , n , l , ans ;
long long int k ;
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
for(i = 0 ; i < n ; i++)
{
scanf("%lld", &p[i]);
p[i] *= p[i] ;
}
sort(p,p+n);
/*for(i = 0 ; i < n ; i++)
printf("%lld ", p[i]);
printf("\n");*/
memset(num,0,sizeof(num));
k = -1 ;
l = 0 ;
for(i = 0 ; i < n ; i++)
{
if(p[i] != k)
{
num[i] = 1 ;
l = i ;
k = p[i] ;
}
else
num[l]++ ;
}
k = -1 ;
for(i = 0 ; i < n ; i++)
if(num[i] == 0)
num[i] = k ;
else
k = num[i] ;
/*for(i = 0 ; i < n ; i++)
printf("%d ", num[i]);
printf("\n");*/
ans = 0 ;
for(i = 0 ; i < n ; i++)
{
for(j = i+1 ; j < n ; j++)
{
k = p[i]+ p[j] ;
int low = 0 , mid , high = n-1 ;
while(low <= high)
{
mid = (low + high) / 2 ;
if( p[mid] == k )
break;
else if( p[mid] < k )
low = mid + 1 ;
else
high = mid - 1 ;
}
if(p[mid] == k)
ans++ ;
}
}
printf("%d\n", ans);
}
}
这篇关于2862--勾股定理的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
