hdu 3939 (피타 고 라 스 + 배척)

제목:
정수 L (L < = 1e 12) 을 지정 하고 (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 을 구하 고 그들 을 판단 하면 된다.
참고 지식
① 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;
}