HDU 3939 毕达哥拉斯三元组

题意：求形成直角三角形切个边长小于L的个数，并且三边两两互素。

也就是求前L本原毕达哥拉斯三元组解的个数。令，其中m>n,。

由上式得z为直角三角形斜边且z<=L

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define maxn 1000008
bool isprime[maxn];
int prime[maxn],nprime,phi[maxn];
void getprime()
{
    long long i,j;
    memset(isprime,1,sizeof(isprime));
    nprime=0;
    for(i=2; i<maxn; i++)
        if(isprime[i])
        {
            prime[nprime++]=i;
            for(j=i*i; j<maxn; j+=i)
                isprime[j]=0;
        }
}
void getphi()
{
    for(int i=1; i<maxn; i++) phi[i]=i;
    for(int i=2; i<maxn; i+=2) phi[i]>>=1;
    for(int i=3; i<maxn; i+=2)
        if(phi[i]==i)
            for(int j=i; j<maxn; j+=i)
                phi[j]=phi[j]/i*(i-1);
}
int check[35],num;
long long ans;
void getcheck(int x)
{
    num=0;
    int d=x;
    if(isprime[x])
    {
        check[num++]=x;
        return;
    }
    for(int i=0; prime[i]*prime[i]<=x; i++)
        if(d%prime[i]==0)
        {
            check[num++]=prime[i];
            while(d%prime[i]==0)d/=prime[i];
        }
    if(d>1&&isprime[d]) check[num++]=d;
}
void dfs(int k,int r,int s,int n)
{
    if(k==num)
    {
        if(r&1) ans-=n/s;
        else ans+=n/s;
        return;
    }
    dfs(k+1,r,s,n);
    dfs(k+1,r+1,s*check[k],n);
}
int main()
{
    int t;
    long long l;
    getprime();
    getphi();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%I64d",&l);
        ans=0;
        int m=sqrt(double(l-1));
        for(int i=m; i>0; i--)
        {
            int p=sqrt(double(l-(long long)i*i));
            if(i&1)
            {
                getcheck(i);
                if(p<i) dfs(0,0,1,p>>1);
                else dfs(0,0,1,i>>1);
            }
            else
            {
                if(i<p) ans+=phi[i];
                else getcheck(i),dfs(0,0,1,p);
            }
        }
        printf("%I64d\n",ans);
    }
    return 0;
}