题目链接：https://nanti.jisuanke.com/t/A1956
题目大意：定义f[i]函数代表i=a * b的对数，其中a和b都不能是平方数的倍数，a * b与b * a不相同，t组样例，给出n，求1~n的f[i]之和。

思路：
整除分块：
1.我们可以用整除分块求出1-n的所有数的因子个数。那么就是所有的i=a*b的对数。然后我们考虑怎么把不满足条件的对数去掉。

2.i=a * b对于每个平方数的倍数x。他可以作为a或者b。x会对所有的x的倍数产生2个不合法的贡献。如果我们把所有的[1, 2e7]的x筛出来。用整除分块求不合法的贡献。

3.我们看2可以发现我减多了。例如36=4 * 9。4和9都减了一次贡献。那么就是说两个数都是平方数的倍数时，会减多。我们必须加回来。这个怎么算？我们还是考虑对于一个数x。他一共有n/x个倍数。分别是x, x * 2, x * 3, x * 4....x * (n/i)，那么我们只要知道1-(n/i)有但是个平方数的倍数就知道这个数多减了多少贡献。当然也是用分块。

线性筛
我们打几个表就会发现：
1.i是素数： f[i]=2
2.f[i]是积性函数
2.假设i最小素因子是e。如果i%(e^k)==0并且k==2, f[i]/=4
3.假设i最小素因子是e。如果i%(e^k)==0并且k>=3, f[i]=0
既然f[i]是积性函数并且只和最小素因子有关，那我们用欧拉筛就可以搞了。

#include <bits/stdc++.h>
#define LL long long
using namespace std;

int siz[20000005];
void init(){
    for(int i=2; i*i<=20000000; i++){
        //说明一定是i*i的因数已经筛过。那么所有的i*i的倍数一定被筛过了。
        if(siz[i*i]) continue;
        for(int k=i*i; k<20000000; k+=i*i){
            siz[k]=1;
        }
    }
    for(int i=2; i<=20000000; i++){
        siz[i]+=siz[i-1];
    }
}

LL cut(LL n){
    LL ans=0;
    for(int l=1; l<=n; ){
        int r=n/(n/l);
        ans+=1ll*(r-l+1)*(n/l);//求所有的贡献
        ans-=2ll*(siz[r]-siz[l-1])*(n/l);//减去x是a或者b的贡献
        ans+=1ll*(siz[r]-siz[l-1])*(siz[n/l]);//容斥把减多的加回来
        l=r+1;
    }
    return ans;
}

int main(){
    init();
    int T; scanf("%d", &T);
    while(T--){
        int n; scanf("%d", &n);
        printf("%lld\n", cut(n));
    }

    return 0;
}

#include <bits/stdc++.h>
#define LL long long
using namespace std;

LL siz[20000005], prime[20000005], tot;
bool vis[20000005];
void init(int N){
    tot=0; siz[1]=1;
    for(int i=2; i<=N; i++){
        if(!vis[i]){
            prime[tot++]=i;
            siz[i]=2;
        }
        for(int j=0; j<tot&&prime[j]*i<=N; j++){
            siz[i*prime[j]]=siz[i]*siz[prime[j]];//积性函数
            vis[i*prime[j]]=1;
            if(i%prime[j]==0){//假设i最小素因子是e。如果i%(e^k)==0并且k==2, f[i]/=4
                siz[i*prime[j]]/=4;
            }
            if(i%(prime[j]*prime[j])==0){//假设i最小素因子是e。如果i%(e^k)==0并且k>=3, f[i]=0
                siz[i*prime[j]]=0;
            }
            if(i%prime[j]==0){
                break;
            }
        }
    }
    for(int i=1; i<=N; i++){
        siz[i]+=siz[i-1];
    }
}

int main(){
    init(200);
    int T; scanf("%d", &T);
    while(T--){
        int n; scanf("%d", &n);
        printf("%lld\n", siz[n]);
    }

    return 0;
}