hdu5833 Zhu and 772002 （高斯消元的简单应用）

太过爱你忘了你带给我的痛 2022-09-25 06:21 10阅读 0赞

hdu5833 Zhu and 772002 （高斯消元的简单应用）：[http://acm.hdu.edu.cn/showproblem.php?pid=5833][http_acm.hdu.edu.cn_showproblem.php_pid_5833]

题面描述：

# Zhu and 772002 #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)  
Total Submission(s): 520 Accepted Submission(s): 174**

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

题目大意：

输入n个数，范围在10的18次方以内，将其质因数分解之后他们的质因子都在2000以内，从中选出1-多个，使得所选数的乘积为完全平方数，计算一共有多少种选法。

题目分析：

不超过2000的素因子，可以考虑每个数的唯一分解式，用01向量表示一个数，再用n个01变量xi来表示我们的选择，其中xi=1表示要选第i个数，xi=0表示不选它，则可以对每个素数的幂列出一个模2的方程。

![Center][]

代码实现如下：

#include <iostream>
    #include <algorithm>
    #include <stdio.h>
    #include <string.h>
    #include <math.h>
    
    using namespace std;
    
    const long long mod=1000000007;
    
    long long equ,var;
    long long a[330][330];
    long long x[330];
    long long free_x[330];
    long long free_num;
    
    int Gauss()
    {
        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;
    }
    
    const int MAXN = 2200;
    long long prime[MAXN+1];
    void getPrime()
    {
        memset(prime,0,sizeof(prime));
        for(int i = 2; i <= MAXN; i++)
        {
            if(!prime[i])prime[++prime[0]] = i;
            for(int j = 1; j <= prime[0] && prime[j] <= MAXN/i; j++)
            {
                prime[prime[j]*i] = 1;
                if(i%prime[j] == 0)break;
            }
        }
    }
    
    long long quick_mod(long long a,long long b)
    {
        long long ans=1;
        while(b)
        {
            if(b&1)
            {
                ans=(ans*a)%mod;
                b--;
            }
            b/=2;
            a=a*a%mod;
        }
        return ans;
    }
    
    long long data[330];
    char str1[330],str2[330];
    
    int main()
    {
        getPrime();
        int T,m;
        int casenum=1;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d",&m);
            {
                for(int i = 0; i < m; i++)
                    scanf("%lld",&data[i]);
                int t=303;
                equ = t;
                var = m;
                for(int i = 0; i < t; i++)
                    for(int j = 0; j < m; j++)
                    {
                        int cnt = 0;
                        while(data[j]%prime[i+1] == 0)
                        {
                            cnt++;
                            data[j] /= prime[i+1];
                        }
                        a[i][j] = (cnt&1);
                    }
                for(int i = 0; i < t; i++)
                    a[i][m] = 0;
                int ret = Gauss();
                long long ansans=quick_mod(2,free_num);
                ansans=(ansans-1)%mod;
                printf("Case #%d:\n",casenum++);
                printf("%lld\n",ansans);
            }
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_5833]: http://acm.hdu.edu.cn/showproblem.php?pid=5833
[Center]: /images/20220718/a0439adc3c4045368e172ef629cbcba1.png