hdu 5833 Zhu and 772002 高斯消元

Zhu and 772002

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

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

Sample Output

Case #1:
3
Case #2:
3

Author

UESTC

Source

2016中国大学生程序设计竞赛 - 网络选拔赛

大白161；kuangbin模板

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<set>
#include<map>
using namespace std;
#define LL long long
#define pi (4*atan(1.0))
#define eps 1e-14
#define bug(x)  cout<<"bug"<<x<<endl;
const int N=1e5+10,M=2e6+10,inf=1e9+10;
const LL INF=1e18+10,mod=1e9+7;

vector<int>p;
//对2取模的01方程组
const int MAXN = 310;
//有equ个方程，var个变元。增广矩阵行数为equ,列数为var+1,分别为0到var
int a[MAXN][MAXN]; //增广矩阵
int x[MAXN]; //解集
int free_x[MAXN];//用来存储自由变元（多解枚举自由变元可以使用）
int free_num;//自由变元的个数

//返回值为-1表示无解，为0是唯一解，否则返回自由变元个数
int Gauss(int var,int equ)
{
    int max_r,col,k;
    free_num = 0;
    for(k = 0, col = 0 ; k < equ && col < var ; k++, col++)
    {
        max_r = k;
        for(int i = k+1;i < equ;i++)
        {
            if(abs(a[i][col]) > abs(a[max_r][col]))
                max_r = i;
        }
        if(a[max_r][col] == 0)
        {
            k--;
            free_x[free_num++] = col;//这个是自由变元
            continue;
        }
        if(max_r != k)
        {
            for(int j = col; j < var+1; j++)
                swap(a[k][j],a[max_r][j]);
        }
        for(int i = k+1;i < equ;i++)
        {
            if(a[i][col] != 0)
            {
                for(int j = col;j < var+1;j++)
                    a[i][j] ^= a[k][j];
            }
        }
    }
    for(int i = k;i < equ;i++)
        if(a[i][col] != 0)
            return -1;//无解
    if(k < var) return var-k;//自由变元个数
    //唯一解，回代
    for(int i = var-1; i >= 0;i--)
    {
        x[i] = a[i][var];
        for(int j = i+1;j < var;j++)
            x[i] ^= (a[i][j] && x[j]);
    }
    return 0;
}
int prime(int x)
{
    for(int i=2;i*i<=x;i++)
    if(x%i==0)return 0;
    return 1;
}
void init()
{
    for(int i=2;i<=2000;i++)
    if(prime(i))p.push_back(i);
}
LL qpow(LL a,LL b,LL c)
{
    LL ans=1;
    while(b)
    {
        if(b&1)ans*=a,ans%=c;
        a=(a*a)%c;
        b>>=1;
    }
    return ans;
}
int main()
{
    init();
    int T,cas=1;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        memset(x,0,sizeof(x));
        memset(a,0,sizeof(a));
        for(int i=0;i<n;i++)
        {
            LL x;
            scanf("%lld",&x);
            for(int j=0;j<p.size();j++)
            {
                while(x%p[j]==0)
                {
                    a[j][i]++;
                    x/=p[j];
                }
                a[j][i]%=2;
            }
        }
        int x=Gauss(n,p.size());
        LL ans=qpow(2LL,x,mod)+mod-1;
        ans%=mod;
        printf("Case #%d:
%lld
",cas++,ans);
    }
    return 0;
}