[原创]hdu 5833 Zhu and 772002 2016中国大学生程序设计竞赛 - 网络选拔赛1002 [质因子分解+高斯消元]【数论】

2016-08-15 09:35:35 Tabris_ 阅读数：309

博客爬取于2020-06-14 22:43:49
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52208349

题目连接：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): 446 Accepted Submission(s): 147

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这么长的序列 然后从中选至少一个数 让这些数的乘积为完全平方数 问有多少种选法

题目分析：
首先注意题目说的 a[i]的最大质因子不会超过2000 这也是在提示你要质因子分解 分解就简单处理一下分解就行了 怎么分都行
这里首先想到的就应该是算数基本定理
A=p1^a1p2^a2p3^a3*…pn^an (pn是质数)
然后分解的时候怎么怎么存储数据?,怎么操作呢?
首先要想这个问题
几个数相乘的结果如果是完全平方数 有什么特点呢?
说白了就是开方后能得到一个整数
比如说B=a1a2; B,a1,a2都为整数 且a1==a2
那么a1和a2 他们质因子分解后是完全一样的
那么B的算是基本定理展开就等于a1的算是基本定理展开乘上a2的算是基本定理展开
那么可以肯定的是B的算是基本定理展开 an一定是偶数的 所以就能拆成两个a1 a2
那么反过来说只要B的算是基本定理展开 an都是偶数 就一定是完全平方数
那么在判断的时候就只要判断an的值的奇偶性就可以了
于是我们就开了这样的数组factor[n+10][333] (2000以内的质数只有303个)
把每个数转化为了一个2进制数
我们可以把题目转化成求n个数中的k个数数异或为0的情况数。使用x1—xn表示最终第i堆石子到底取不取（1取，0不取），将每堆石子数画成2进制的形式，列成303个方程来求自由变元数，最后由于自由变元能取1、0两种状态
然后直接高斯消元就可以了
最后的结果就是 2^(自由元)-1

注: 最终结果减去的那个一 减去的是1个都不选则情况下的0

附本题代码
-----------------------------------.

hdu 5833
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

# include <cstdio>
# include <cstdlib>
# include <cmath>
# include <cstring>
# include <string>
# include <queue>
# include <map>
# include <iostream>
# include <algorithm>
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;

const int MOD = 1000000007;

# define weishu k


int prime[50000];
int Is_or[20100];
int k;
void Prime()
{
    int n=2001;
    k=0;
    memset(Is_or,1,sizeof(Is_or));
    Is_or[0]=Is_or[1]=0;
    for(int i=2; i<n; i++)
    {
        if(Is_or[i])
        {
            prime[k++]=i;
            for(int j=i+i; j<n; j+=i)
            {
                Is_or[j]=0;
            }
        }
    }
    return ;
}


LL a[333];

LL  g[333][333];

int Gauss(int n)
{
    int i, j, r, c, cnt;
    for (c = cnt = 0; c < n; c++)
    {
        for (r = cnt; r < weishu; r++)
        {
            if (g[r][c])
                break;
        }
        if (r < weishu)
        {
            if (r != cnt)
            {
                for (i = 0; i < n; i++)
                {
                    g[r][i]^=g[cnt][i];
                    g[cnt][i]^=g[r][i];
                    g[r][i]^=g[cnt][i];
                }
            }
            for (i = cnt + 1; i < weishu; i++)
            {
                if (g[i][c])
                {
                    for (j = 0; j < n; j++)
                        g[i][j] ^= g[cnt][j];
                }
            }
            cnt++;
        }
    }
    return n - cnt;
}
LL qmod (LL a,LL b)
{
    LL res = 1;
    while(b)
    {
        if(b&1)  res=(res*a)%MOD;
        b >>= 1;
        a=(a*a)%MOD;
    }
    return res;
}
int main()
{
    Prime();
    int c,p=0;
    int n, i, j;

    scanf("%d", &c);
    while (c--)
    {
        int fuck = 0;
        scanf("%d", &n);
        memset(g,0,sizeof(g));
        LL temp;
        for(int i=0; i<n; i++)
        {
            scanf("%I64d",&a[i]);
            temp=a[i];
            for(int j=0; j<k; j++)
            {
                if(temp<prime[j]) break;
                while(temp%prime[j]==0)
                {
                    temp/=prime[j];
                    g[j][i]++;
                }
                g[j][i]%=2;
            }
        }
        LL ans, vary;
        vary = Gauss(n);
        printf("Case #%d:\n",++p);
        ans = qmod(2,vary);
        printf("%I64d\n",(ans-1)%MOD);
    }
    return 0;
}