?

題目傳送門

題意：給n個(gè)數(shù)，選擇一些數(shù)字乘積為平方數(shù)的選擇方案數(shù)。訓(xùn)練指南題目。

分析：每一個(gè)數(shù)字分解質(zhì)因數(shù)。比如4， 6， 10， 15，,?,?,?, 令，表示選擇第i個(gè)數(shù)字，那么，如果p是平方數(shù)，那么每個(gè)質(zhì)因數(shù)上的指數(shù)為偶數(shù)，x1系數(shù)為2已經(jīng)是偶數(shù)不考慮?？梢赞D(zhuǎn)換為異或?yàn)?判斷偶數(shù)，即奇數(shù)置為1，偶數(shù)置為0，然后n個(gè)數(shù)字m個(gè)質(zhì)因數(shù)的增廣矩陣消元看有幾個(gè)自由變量(取0或1無所謂)，答案是2^r - 1(全部都不取方案不算)

#include <bits/stdc++.h>const int N = 500 + 5; bool vis[N]; int prime[N]; int A[N][105];void sieve(int n) {int m = sqrt (n + 0.5);for (int i=2; i<=m; ++i) {if (!vis[i]) {for (int j=i*2; j<=n; j+=i) {vis[j] = true;}}} }int gen_prime(int n) {memset (vis, false, sizeof (vis));sieve (n);int c = 0;for (int i=2; i<=n; ++i) {if (!vis[i]) {prime[c++] = i;}}return c; }int rank(int m, int n) {int i = 0, j = 0;while (i < m && j < n) {int r = i;for (int k=i; k<m; ++k) {if (A[k][j]) {r = k;break;}}if (A[r][j]) {if (r != i) {//!for (int k=0; k<=n; ++k) {std::swap (A[r][k], A[i][k]);}}for (int k=i+1; k<m; ++k) {if (A[k][j]) {for (int c=i; c<=n; ++c) {A[k][c] ^= A[i][c];}}}++i;}++j;}return i; }//Running_Time int main() {int T; scanf ("%d", &T);int m = gen_prime (500);while (T--) {int n; scanf ("%d", &n);memset (A, 0, sizeof (A));int maxp = 100;for (int i=0; i<n; ++i) {long long x; scanf ("%lld", &x);for (int j=0; j<m; ++j) {while (x % prime[j] == 0) {x /= prime[j];A[j][i] ^= 1;maxp = std::max (maxp, j);}}}int r = rank (maxp+1, n);std::cout << ((1LL << (n - r)) - 1) << '\n';}return 0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/Running-Time/p/5365681.html

總結(jié)

以上是生活随笔為你收集整理的xor方程组消元 UVA 11542 Square的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。