本文共 1720 字，大约阅读时间需要 5 分钟。

题目大意

现在给出无平方数的定义，就是一个数唯一分解后因子的幂次不能大于$1$。但是本题问的是一个数如果分为两个无平方数的乘积，求有多少种情况

分析

实际上无平方数就是莫比乌斯函数$\mu (n)!=0$的情况。对于一个数$n$，能分解为两个无平方数的乘积当且仅当$n$唯一分解的幂次中不大于$2$。然后我们发现对于给出质因子，无非就是分到第一组或者第二组累乘，如果该质因子的幂次为$1$，显然需要总的方案数会乘以二；如果幂次为$2$，只能各分一个，相当于无贡献

本题给出的范围明显是需要筛法解决，因为无平方数类似于求莫比乌斯函数，考虑欧拉线性筛，因为每个数只会被筛一次，那么我们可以通过每次操作，类似于动规那样更新，时间复杂度$O(n)$

//// Created by Happig on 2020/9/18//#include 
   
    #include 
    
     #include 
     
      using namespace std;#define fi first#define se second#define pb push_back#define ins insert#define Vector Point#define ENDL "\n"#define lowbit(x) (x&(-x))#define mkp(x, y) make_pair(x,y)#define mem(a, x) memset(a,x,sizeof a);typedef long long ll;typedef long double ld;typedef unsigned long long ull;typedef pair
      
        pii;typedef pair
       
         pll;typedef pair
        
          pdd;const double eps = 1e-8;const double pi = acos(-1.0);const int inf = 0x3f3f3f3f;const double dinf = 1e300;const ll INF = 1e18;const int Mod = 1e9 + 7;const int maxn = 2e7 + 10;vector
         
           prime;bitset
          
            vis;ll f[maxn], sum[maxn];void init() { vis.reset(); f[1] = 1; for (int i = 2; i < maxn; i++) { if (!vis[i]) { prime.push_back(i); f[i] = 2; } for (int j = 0; j < prime.size() && i * prime[j] < maxn; j++) { vis[i * prime[j]] = 1; if (i % prime[j]) { f[i * prime[j]] = f[i] * 2; } else { if (i % (prime[j] * prime[j]) == 0) f[i * prime[j]] = 0; else f[i * prime[j]] = f[i] / 2; break; } } }}int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t, n; init(); for (int i = 1; i < maxn; i++) { sum[i] = sum[i - 1] + f[i]; } cin >> t; while (t--) { cin >> n; cout << sum[n] << ENDL; } return 0;}