UESTC 618 无平方因子数 ( 莫比乌斯)

UESTC 618

题意：求1到n中无平方因子数的个数

Sample Input

3 
1 
10 
30

Sample Output

1 
7 
19

思路：与前面的BZOJ 2440相似

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <queue>

#include <vector>

#include <algorithm>

#include <functional>

typedef long long ll;

using namespace std;

const int inf = 0x3f3f3f3f;

const int maxn = 1e6+10;

int tot;

int is_prime[maxn];

int mu[maxn];

int prime[maxn];

void Moblus()

{

    tot = 0;

    mu[1] = 1;

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

    {

        if(!is_prime[i])

        {

            prime[tot++] = i;

            mu[i] = -1;

        }

        for(int j = 0; j < tot && i*prime[j] < maxn; j++)

        {

            is_prime[i*prime[j]] = 1;

            if(i % prime[j])

            {

                mu[i*prime[j]] = -mu[i];

            }

            else

            {

                mu[i*prime[j]] = 0;

                break;

            }

        }

    }

}

int main()

{

    Moblus();

    int T;

    ll n;

    scanf("%d",&T);

    while(T--)

    {

        ll ans = 0;

        scanf("%lld",&n);

        for(ll i = 1;i*i <= n;i++)

            ans += (ll)mu[i]*(n/(i*i));

        printf("%lld\n",ans);

    }

}