不知道线性基是什么东西的可以看看蒟蒻的

题意：

给你n个数，每个数<=70，问有多少个集合，满足集合中所有数相乘是个完全平方数（空集除外）

题解：

完全看不出这玩意儿和线性基有什么关系……我可能太菜了……

首先，一个完全平方数分解质因数之后每个质因子都出现偶数次

又因为小于等于$70$的质数总共18个，可以用18位的二进制表示，0表示偶数次，1表示奇数次

那么两个数相乘就是每一个质因子表示的位的异或

那么就是求有多少种方法相乘得0

首先求出原数组的线性基，设$cnt$表示线性基内数的个数

那么答案就是$2^{n-cnt}-1$

证明：线性基内的数是最小线性无关组

那么除了线性基内的所有数的子集都能被线性基内的数张成（就是表示出来）

那么上面的所有子集和张成相等，两者异或起来为0

所以把线性基内的数除去，剩下的数的所有子集都能与线性基内的数异或成0

那么答案就是真子集个数

1 //minamoto 2 #include
     
       3 #include
      
        4 using namespace std; 5 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 6 char buf[1<<21],*p1=buf,*p2=buf; 7 inline int read(){ 8     #define num ch-'0' 9     char ch;bool flag=0;int res;10     while(!isdigit(ch=getc()))11     (ch=='-')&&(flag=true);12     for(res=num;isdigit(ch=getc());res=res*10+num);13     (flag)&&(res=-res);14     #undef num15     return res;16 }17 const int N=1e5+5,M=20,mod=1e9+7;18 int p[]={
   2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67};19 int b[M],a[N],n,cnt;20 inline int ksm(int x,int y){21     int res=1;22     while(y){23         if(y&1) res=1ll*res*x%mod;24         x=1ll*x*x%mod,y>>=1;25     }26     return res;27 }28 void insert(int x){29     for(int i=18;i>=0;--i){30         if(x>>i&1){31             if(!b[i]){b[i]=x;break;}32             x^=b[i];33         }34     }35 }36 int main(){37 //    freopen("testdata.in","r",stdin);38     n=read();39     for(int i=1;i<=n;++i){40         int x=read();41         for(int j=0;j<=18;++j){42             if(x%p[j]==0){43                 int now=0;44                 while(x%p[j]==0) x/=p[j],now^=1;45                 a[i]|=now<