题目链接：

这个题目也是2016年CCPC网赛上面的题目，当时我是不会做的，但是大牛们都知道这是一个原题，最后给一队过了，还是大牛们厉害，其实也不是很难。

 

题意：

给出n个正整数，从中选出1个或者多个，使得选出来的整数乘积是完全平方数，一共有多少种选法。

 

分析：

"不含大于500的素数因子"——每一个数的唯一分解式。

例如： {4,6,10,15} 

4^x1 = 2² * 3⁰ * 5⁰;

6^x2 = 2¹ * 3¹ * 5⁰;

10^x3= 2¹ * 3⁰ * 5¹;

15^x4 = 2⁰* 3¹ * 5¹;

要使得乘积为平方数，那么每个分向量的指数为偶数。

就得到了方程组：

x2 + x3 = 0(mod2);

x2 + x4 = 0(mod2);

x3 + x4 = 0(mod2);

解方程：

发现有x个自由变量答案就是 2^x - 1个解(全部不要题意删除);

 

#include 
      
       using namespace std;const int maxn = 500 + 10;const int maxp = 100;int vis[maxn];int prime[maxp];int gen_primes(int n){    int m = (int)sqrt(n+0.5);    memset(vis,0,sizeof(vis));  //是素数为 0    for(int i=2; i<=m; i++)    {        if(!vis[i])        {            for(int j=i*i; j<=n; j+=i)                vis[j] = 1;        }    }    int c = 0;    for(int i=2; i<=n; i++)    {        if(!vis[i])            prime[c++] = i;    }    return c;}typedef int Matrix[maxn][maxn];Matrix A;//m 个 方程组，n 个变元int ranks(Matrix A,int m,int n){    int i=0,j=0,k,r,u;    while(i