51nod 1165 整邊直角三角形的數量 【數學：公式--求約數】

1165 整邊直角三角形的數量

基準時間限制：2 秒 空間限制：131072 KB 分值: 160 

難度：6級算法題

 收藏

 關注

直角三角形，三條邊的長度都是整數。給出周長N，求符合條件的三角形數量。

例如：N = 120，共有3種不同的滿足條件的直角3角行。分别是： {20,48,52}, {24,45,51}, {30,40,50}。

Input

第1行：一個數T，表示後面用作輸入測試的數的數量。（1 <= T <= 50000)第2 - T + 1行：每行1個數N(12 <= N <= 10^7)。

Output

輸出共T行，每行1個對應的數量。

Input示例

212013

Output示例

30

0.0

知道b的範圍後---求n^2的約數---判定就行啦------

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
double sq;
struct node{
    int ge,shu;
}yyy[12000];
int lp,kp,zp;
LL yue[60000],zhi[6000];
void yu(int n)
{
    for (int i=0;i<zp&&zhi[i]<=n;i++)
    {
        if (n%zhi[i]==0)
        {
            yyy[lp].ge=0;
            while (n%zhi[i]==0)
            {
                yyy[lp].ge+=2;
                n/=zhi[i];
            }
            yyy[lp++].shu=zhi[i];
        }
    }
    if (n!=1)
    {
        yyy[lp].ge=2;
        yyy[lp++].shu=n;
    }
}
void slove()
{
    LL l,n,n2;
    scanf("%lld",&n);
    if (n%2)
    {
        printf("0\n");
        return ;
    }
    lp=0,kp=0;
    yu(n);//求約數
    yue[kp++]=1;
    for (int i=0;i<lp;i++)
    {
        int k=kp;
        int kk=yyy[i].ge;
        LL cheng=1;
        while (kk--)
        {
            cheng*=yyy[i].shu;
            for (int j=0;j<k;j++)
            {
                if (yue[j]*cheng>=2*n) continue;
                yue[kp++]=yue[j]*cheng;
            }
        }
    }
    sort(yue,yue+kp);//n^2的<2n的約數--n
    l=int(sq*n);n2=2*n;
    int kai=upper_bound(yue,yue+kp,l)-yue;
    LL ans=0,b,a,c;
    for (int i=kai;i<kp;i++)
    {
        if (yue[i]==yue[i-1]||(yue[i]&1)||(n*n)%yue[i]!=0) continue;
        b=n-(n*n/yue[i]);
        a=n-yue[i]/2;
        c=yue[i]/2-b;
        if (a>0&&a<=b&&b<c)
        {
            ans++;
        }
    }
    printf("%lld\n",ans);
}
void ss()
{
    bool fafe[4000];zp=0;
    memset(fafe,true,sizeof(fafe));
    for (int i=2;i<4000;i++)
    {
        if (fafe[i])
        {
            zhi[zp++]=i;
            for (int j=i*i;j<4000;j+=i)
                fafe[j]=false;
        }
    }
}
int main()
{
    ss();
    sq=sqrt(2.0);
    int t;scanf("%d",&t);
    while (t--)
    slove();
    return 0;
}