传送门

Zhu and 772002

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 48    Accepted Submission(s): 16 Problem Description Zhu and 772002 are both good at math. One day, Zhu wants to test the ability of 772002, so he asks 772002 to solve a math problem. But 772002 has a appointment with his girl friend. So 772002 gives this problem to you. There are n numbers a1,a2,...,an. The value of the prime factors of each number does not exceed 2000 , you can choose at least one number and multiply them, then you can get a number b . How many different ways of choices can make b is a perfect square number. The answer maybe too large, so you should output the answer modulo by 1000000007 .   Input First line is a positive integer T , represents there are T test cases. For each test case: First line includes a number n(1≤n≤300) ，next line there are n numbers a1,a2,...,an,(1≤ai≤1018).   Output For the i-th test case , first output Case #i: in a single line. Then output the answer of i-th test case modulo by 1000000007 .   Sample Input 2 3 3 3 4 3 2 2 2   Sample Output Case #1: 3 Case #2: 3   Author UESTC   Source 2016中国大学生程序设计竞赛 - 网络选拔赛

题目大意：

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

法？对 MOD 取模。

解题思路：

赛后群里说 原题，已然蒙逼，刘汝佳白书 P160 , 一样一样的！！！，唉，亏我们还在推了那么

久。。。

其实我是做过一个类似的题所以没用多长时间，那个题目链接传送门

其实，那个题跟这个题目是差不多的，看那个题目就可以了，这个题目就是在那个题目的基础上先

处理一下就行了。。。

My Code：

/** 2016 - 08 - 14 下午 Author: ITAK Motto: 今日的我要超越昨日的我，明日的我要胜过今日的我， 以创作出更好的代码为目标，不断地超越自己。 **/ #include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <vector> #include <queue> #include <algorithm> #include <set> using namespace std; typedef long long LL; typedef unsigned long long ULL; const LL INF = 1e9+5; const LL MAXN = 2e3+5; const LL MOD = 1e9+7; const double eps = 1e-7; const double PI = acos(-1); using namespace std; /**+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/ LL equ, var;///equ个方程 var个变量 LL a[MAXN][MAXN];///增广矩阵 LL x[MAXN];///解的数目 bool free_x[MAXN];///判断是不是自由变元 LL free_num;///自由变元的个数 inline LL GCD(LL m, LL n) { if(n == 0) return m; return GCD(n, m%n); } inline LL LCM(LL a, LL b) { return a/GCD(a,b)*b; } LL Gauss() { LL Max_r;///当前列绝对值最大的存在的行 ///col：处理当前的列 LL row=0; for(LL col=0; row<equ&&col<var; row++,col++) { Max_r = row; for(LL i=row+1; i<equ; i++) if(abs(a[i][col]) > abs(a[Max_r][col])) Max_r = i; if(Max_r != row) for(LL i=0; i<var+1; i++) swap(a[row][i], a[Max_r][i]); if(a[row][col] == 0) { row--; continue; } for(LL i=row+1; i<equ; i++) { if(a[i][col]) { for(LL j=col; j<var; j++) { a[i][j] ^= a[row][j]; } } } } return row; } const LL MAX = 2e3+5; LL p[MAX]; bool prime[MAX]; LL k; void isprime() { k = 0; memset(prime, false, sizeof(prime)); for(LL i=2; i<MAX; i++) { if(!prime[i]) { p[k++] = i; for(LL j=i*i; j<MAX; j+=i) prime[j] = true; } } } LL quick_mod(LL a, LL b) { LL ans = 1; while(b) { if(b & 1) ans = (ans*a)%MOD; b>>=1; a = (a*a)%MOD; } return ans; } int main() { isprime(); equ = k; LL T, n; scanf("%I64d",&T); for(LL cas=1; cas<=T; cas++) { cin>>var; memset(a, 0, sizeof(a)); for(LL i=0; i<var; i++) { LL x; LL sum; scanf("%I64d",&x); for(LL j=0; j<equ; j++) { sum = 0; if(x%p[j] == 0) { LL mm = x; while(mm%p[j]==0) { sum++; mm /= p[j]; } } ///构造系数矩阵 if(sum & 1) a[j][i] = 1; else a[j][i] = 0; } } LL ans = var - Gauss(); LL ret = quick_mod(2LL, ans); ret--; ret = (ret%MOD+MOD)%MOD; printf("Case #%I64d:\n%I64d\n",cas,ret); } return 0; }