HDU 5833 高斯消元

本文主要是介绍HDU 5833 高斯消元，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

n个数，任选>=1个数相乘，使得乘积是完全平方数。

其实就是开关，控制灯泡。

数 ----第i个质因子p的个数%2  = {1 ， 0}

==

开关----第i个灯泡 = {开 ， 关}

最后使得所有灯泡都是灭着的方案数 = 2^自由变元个数  

全部关着的情况     ==   一个数也不选   应省去

import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.StringTokenizer;public class Main {public static void main(String[] args){new HDU5833().solve()  ; }
}class HDU5833{InputReader in = new InputReader(System.in) ;PrintWriter out = new PrintWriter(System.out) ;final int N = 2000 ;int[] prime = new int[N] ;int primeSize ;boolean[] is = new boolean[N] ;{Arrays.fill(is , false) ;primeSize = 0 ;for(int i = 2 ; i < N ; i++){if(! is[i]) prime[primeSize++] = i ;for(int j = 0 ; j < primeSize && prime[j] * i < N ; j++){is[i * prime[j]] = true ;if(i % prime[j] == 0) break ; }}}final int MAXN = 318 ;int[][] A = new int[MAXN][MAXN] ;int gauss(int n){int col , cnt = 0 , row ; for(col = 0  ; col < n ; col++){for(row = cnt ; row < 303 ; row++){if(A[row][col] != 0 ) break ;}if(row < 303){if(row != cnt){for(int i = 0 ; i < n ; i++){int t = A[row][i] ;A[row][i] = A[cnt][i] ;A[cnt][i] = t ;}}for(int i = cnt + 1 ; i < 303 ; i++){if(A[i][col] != 0){for(int j = col ; j < n ; j++)A[i][j] ^= A[cnt][j] ;}}cnt++ ;}}return n - cnt ;}long[] a = new long[MAXN] ;final long MOD = 1000000007L ;void solve(){int t = in.nextInt() ;for(int ca = 1 ; ca <= t ; ca++){int n = in.nextInt() ;for(int i = 0 ; i < n ; i++) a[i] = in.nextLong() ;for(int i = 0 ; i < 303 ; i++){for(int j = 0 ; j < n ; j++){int k = 0 ; while(a[j] % prime[i] == 0){k++ ;a[j] /= prime[i] ;}A[i][j] = k % 2 ;}}int res = gauss(n) ;long ans = 1L ;while(res-- > 0){ans <<= 1 ;ans %= MOD ;}ans = (ans - 1 + MOD) % MOD ;out.println("Case #" + ca + ":") ;out.println(ans) ;}out.flush() ;}
}class InputReader {  public BufferedReader reader;  public StringTokenizer tokenizer;  public InputReader(InputStream stream) {  reader = new BufferedReader(new InputStreamReader(stream), 32768);  tokenizer = new StringTokenizer("");  }  private void eat(String s) {  tokenizer = new StringTokenizer(s);  }  public String nextLine() {  try {  return reader.readLine();  } catch (Exception e) {  return null;  }  }  public boolean hasNext() {  while (!tokenizer.hasMoreTokens()) {  String s = nextLine();  if (s == null)  return false;  eat(s);  }  return true;  }  public String next() {  hasNext();  return tokenizer.nextToken();  }  public int nextInt() {  return Integer.parseInt(next());  }  public long nextLong() {  return Long.parseLong(next());  }  public double nextDouble() {  return Double.parseDouble(next());  }  public BigInteger nextBigInteger() {  return new BigInteger(next());  }  }  

这篇关于HDU 5833 高斯消元的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---