hdu 3939(勾股+容斥)

题意：

给定一个整数L(L<=1e12)，计算(x,y,z)组的个数。其中x<y<z，x^2+y^2=z^2，gcd(x,y)==1,gcd(x,z)==1,gcd(y,z)==1。

思路：

以下的方法可用来找出勾股数。设m>n 、 m 和 n 均是正整数，

a = m^2-n^2    b = 2mn   c = m^2+n^2

若 m 和 n 是互质，而且 m 和 n 其中有一个是偶数，计算出来的 (a, b, c) 就是素勾股数

然后我们需要的便是计算m,n互质 qie m,n一奇一偶

因为 m^2*2 = a+c,所以可以求出m的范围 sqrt(l),然后可以求出n的范围t

于是通过枚举m,并求出n,然后对他们进行判断即可

参考knownothing

①当m为偶数时，

如果m <= t,那么n可以取[1,m]中与m互质的数，因为他们一定是奇数

如果m > t,那么n只能取[1,t]中与m互质的数

②当m为奇数时：

 

如果m <= t,那么n可以取[1,m]中与m/2互质的数,如果ai是[1,m/2]中与m互质的，那么2*ai便是与m互质的偶数

如果m > t,那么n只能取[1,t]中与t/2互质的数

 

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
typedef long double ld;
const ld eps=1e-10;
const int inf = 0x3f3f3f;
const int maxn = 1e6;
const int MOD = 1e9+7;
bool check[maxn+10];
int prime[maxn+10];
int phi[maxn+10];
int factor[105];
int facnum;
int tot;

void phi_and_prime(int N)
{
    memset(check,0,sizeof(check));
    phi[1] = 1;
    tot = 0;

    for(int i = 2; i <= N; i++)
    {
        if(!check[i])
        {
            prime[tot++] = i;
            phi[i] = i - 1;
        }
        for(int j = 0; j < tot; j++)
        {
            if(i*prime[j] > N) break;
            check[i*prime[j]] = true;
            if(i % prime[j] == 0 )
            {
                phi[i*prime[j]] = phi[i] * prime[j];
                break;
            }
            else
            {
                phi[i * prime[j]] = phi[i] * (prime[j]-1);
            }
        }
    }
}


void fac(int x)
{
    int tp = x;
    facnum = 0;
    for(int i = 0; i < tot && prime[i]*prime[i] <= maxn; i++)
    {
        if(tp % prime[i] == 0)
        {
            factor[facnum++] = prime[i];
            while(tp % prime[i] == 0)
            {
                tp /= prime[i];
            }
        }
        if(tp == 1)
            break;
    }
    if(tp > 1)
        factor[facnum ++ ] = tp;
    
    return ;
}


ll ans;
void dfs(int cur,int mul,int tot,int n)      //搜索实现互斥
{
    if(cur == facnum)
    {
        if(tot & 1)  ans = ans - n/mul;
        else ans = ans + n/mul;
        return ;
    }
    dfs(cur+1,mul*factor[cur],tot+1,n);
    dfs(cur+1,mul,tot,n);
}

int main()
{
    int T;
    ll n;
    phi_and_prime(maxn);
    scanf("%d",&T);
    while(T--)
    {
        scanf("%I64d",&n);
        ll p = sqrt(n + 0.5);                            //估计m范围
        ans = 0;
        for(int i = 1; i <= p; i++)                      //枚举
        {
            int q = sqrt(n - (ll)i*i + 0.5);                       //估计n的范围

            if(i % 2)
            {
                fac(i);
                if(q >= i)  dfs(0,1,0,i>>1);
                else dfs(0,1,0,q>>1);
            }
            else
            {
                fac(i);
                if(q >= i) ans += phi[i];
                else dfs(0,1,0,q);
            }
        }
        printf("%I64d
",ans);
    }
    return 0;
}