\(\\\)

---

\(T\)组数据，每次给出一个正整数 \(N\) ，判断其是否能被任意一个完全平方数整除。

• \(T\le 20,N\le 10^{18}\)

\(\\\)

\(Solution\)

---

比较巧妙。

考虑一个数能被完全平方数整除，当且仅当对其分解质因数以后，至少有一个质数的指数\(\ge 2\)。

借用试除法分解质因数的思路，大于\(\sqrt N\)的质因子至多只有一个。那么，大于 \(\sqrt[3] N\) 的质因数的平方整除 \(N\) 的个数至多也只有一个，而且指数至多为 \(2\) ，因为指数再大或者再乘上一个等数量级的完全平方数都会超过 \(10^{18}\) 的数据范围。

然后就筛出 \(\sqrt[3] {10^{18}}=10^6\) 范围内的质数，然后将 \(N\) 中\([0,10^6]\) 范围内的质因子去掉。在这一过程中一旦出现指数大于 \(2\) 的情况就直接 \(GG\) 。然后剩下的如果是大于 \(1\) 的话就 \(check\) 一下是不是完全平方数就好了。

\(\\\)

\(Code\)

---

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define N 1000010#define R register#define gc getcharusing namespace std;typedef long long ll;inline ll rd(){ ll x=0; bool f=0; char c=gc(); while(!isdigit(c)){if(c=='-')f=1;c=gc();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();} return f?-x:x;}bool vis[N];ll prm[N];inline void init(){ for(R ll i=2;i