勾股定理

待我称王封你为后i 2022-08-10 09:58 104阅读 0赞

## 勾股定理 ##

##### 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 <string.h>      
    #include <stdio.h>    
    #include<stdlib.h>       
    int cmp(const void *a,const void *b)    
    {    
       return *(int *)a-*(int *)b;    
    }    
    int  a[1010], b, ls[1010];      
     int f(int  x, int  y)      
    {      
        int  m;      
        while(x < y)      
        {      
             m = x +(y-x) /2;      
            if(ls[m] == b) return 1;      
            else if (ls[m] > b) y = m;      
             else x = m+1;      
         }      
        return -1;      
     }      
    int main()      
    {      
          
        int t;      
       while(~scanf("%d",&t))      
        while(t--)      
        {      
            int n, i, j;      
            scanf("%d",&n);      
            for(i = 0; i < n; i++)      
            {      
                scanf("%d",&a[i]);      
                ls[i] = a[i]*a[i];      
            }      
            qsort(a,n,sizeof(a[0]),cmp);      
            qsort(ls,n,sizeof(ls[0]),cmp);      
            int c = 0;      
             for(i = 0; i < n; i++)      
             {      
                 for(j = i+1; j < n; j++)      
                 {      
                     int k;      
                     b = a[i] *a[i] + a[j] *a[j];      
                     k = f(j,n);      
                     if(k == 1)      
                      c+=k;      
                 }      
             }      
                printf("%d\n",c);      
        }      
        return 0;      
    }