素数筛链接：https://blog.csdn.net/dl962454/article/details/76595623
【题意】
f(i)：能拆成两个数的乘积，并且这两个数要求没有平方因子，并且两个数的位置互换算两种方案。
最后求f(1)+f(2)+f(3)+...f(n）。
【解题思路】
还是对欧拉筛的理解不够透彻，比赛的时候一直是筛完素数再去求解f(i)，其实是可以一边筛一边求解的。
不难发现，当i是素数时，f(i)=2，当i有3个及以上相同因子时，f(i)=0（比如2*2*2*3不可能组合成两个都没有平方因子的数），当i没有相同因子（假设因子数为n）时，f(i)=2^n（比如2*3*5是8个），当i有两个相同因子（假设有p对相同因子，n个不同因子）时，f(i)=2^n/2^p（比如2*2*3*3*5是2个）。
那么最后总结起来再用个欧拉筛就是这样的。
对于素数d：f(d)=2
当d|p时，若d|p^2，则f(d*p)=0，否则f(d*p)=f(d)/2
反之，则f(d*p)=2*f(d)
【代码】
#include <iostream> #include <cstring> #include <cstdio>using namespace std;const int maxn=2e7+10;//1int prime[maxn]; int vis[maxn]; long long f[maxn],ans[maxn];void isprime() {int idx=0;f[1]=1;memset(vis,0,sizeof(vis));for(int i=2;i<maxn;i++){if(!vis[i]){prime[idx++]=i;f[i]=2;}for(int j=0;j<idx&&prime[j]*i<maxn;j++){vis[i*prime[j]]=1;if(i%prime[j]==0){if(i%(prime[j]*prime[j])==0){f[i*prime[j]]=0;}else f[i*prime[j]]=f[i]/2;break;}else f[i*prime[j]]=f[i]*2;}}for(int i=1;i<maxn;i++){ans[i]=ans[i-1]+f[i];} }int main() {ios::sync_with_stdio(false);cin.tie(0);int T,n;isprime();scanf("%d",&T);while(T--){scanf("%d",&n);printf("%lld\n",ans[n]);}return 0; }
