首页 > 代码库 > hdu 5833 Zhu and 772002 高斯消元
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.
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).
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.
Then output the answer of i-th test case modulo by 1000000007.
Sample Input
233 3 432 2 2
Sample Output
Case #1:3Case #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到varint 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:\n%lld\n",cas++,ans); } return 0;}
Zhu and 772002
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1933 Accepted Submission(s): 696
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.
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).
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.
Then output the answer of i-th test case modulo by 1000000007.
Sample Input
233 3 432 2 2
Sample Output
Case #1:3Case #2:3
Author
UESTC
Source
2016中国大学生程序设计竞赛 - 网络选拔赛
hdu 5833 Zhu and 772002 高斯消元
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。