uestc 1720无平方因子数

求素数  然后容斥原理
// n之内有平方因子的数的个数sum =n/(2^2) + n/(3^2)+……+n/(k^2) - n/(2^2 * 3^2)-……+…….

// #pragma comment(linker, "/STACK:1024000000,1024000000")

#include <iostream>

#include <algorithm>

#include <queue>

#include <stack>

#include <math.h>

#include <stdio.h>

#include <string.h>

using namespace std;

#define MOD 1000000007

#define maxn 1000010

#define maxm 1000010

#define LL long long

LL pr[maxn];

int p;

void getprime(){

    int i,j;

    for(i=;i<maxn;i+=) pr[i]=;

    for(i=;i*i<maxn;i+=)

        if(!pr[i])

         for(j=i*i;j<maxn;j+=i)

           pr[j]=;

    pr[p++]=;

    for(i=;i<maxn;i+=)

        if(!pr[i])pr[p++]=i;

}

LL n,m,sum;

void dfs(int id,int dep,LL ji){

    LL tp;

    int i;

    for(i=id;i<p;i++){

        tp=ji*pr[i];

        if(tp>m) return;

        if(dep%)

            sum+=n/(tp*tp);

        else

            sum-=n/(tp*tp);

            dfs(i+,dep+,tp);

    }

}

int main(){

    getprime();

    int T;

    scanf("%d",&T);

    while(T--){

       // scanf("%I64d",&n);

        scanf("%lld",&n);

        m=sqrt(n+1.0);

        sum=;

        dfs(,,);

      //  printf("%I64d\n",n-sum);

        printf("%lld\n",n-sum);

    }

}