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
| package 高斯消元模板; import java.io.*; import java.util.*; public class Main { static boolean[]prime; public static void main(String[] args) { Scanner sc=new Scanner(System.in); PrintWriter pw=new PrintWriter(System.out); makePrime(); int count=0; int[]p=new int[303]; for(int o=1;o<=2000;o++){ if(prime[o]){ p[count]=o; count++; } } int t=sc.nextInt(); for(int o=1;o<=t;o++){ pw.println("Case #"+o+":"); int n=sc.nextInt(); long []shu=new long[n]; for(int i=0;i<n;i++) shu[i]=sc.nextLong(); Gauss gs=new Gauss(303,n); for(int i=0;i<303;i++){ for(int j=0;j<n;j++){ int temp=0; while(shu[j]%p[i]==0){ temp++; shu[j]=shu[j]/p[i]; } if(temp%2==0) gs.A[i][j]=0; else gs.A[i][j]=1; } } int r=gs.gauss(303, n); long ans=1; for(int i=1;i<=n-r;i++){ ans=(ans*2)%1000000007; } pw.println(ans-1); pw.flush(); } } static void makePrime(){ prime=new boolean[2010]; Arrays.fill(prime, true); prime[0]=false; prime[1]=false; for(int i=2;i<2010;i++){ if(prime[i]){ for(int j=i*i;j<2010;j+=i){ prime[j]=false; } } } } } class Gauss{ int A[][]; Gauss(int m,int n){ A=new int[m][n]; } int gauss(int m,int n){ int i=0,j=0,k,r,u; while(i<m&&j<n){ r=i; for(k=i;k<m;k++){ if(A[k][j]!=0){ r=k;break; } } if(A[r][j]!=0){ if(r!=i) swap(A,r,i,n); for(u=i+1;u<m;u++) if(A[u][j]!=0) for(k=i;k<n;k++) A[u][k]^=A[i][k]; i++; } j++; } return i; } static void swap(int[][]A,int r,int i,int n){ for(int k=0;k<n;k++){ int temp=A[r][k]; A[r][k]=A[i][k]; A[i][k]=temp; } } }
|