题目链接:uva 11542 - Square
题目大意:给出n个整数,从中选出1个或多个,使得选出的整数乘积为完全平方数,一共有多少种选法。空集不算。
解题思路:大白数例题。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 500;
typedef long long ll;
typedef int Matrix[maxn+5][maxn+5];
int np, pri[maxn+5], vis[maxn+5];
void prime_table (int n) {
np = 0;
memset(vis, 0, sizeof(vis));
for (int i = 2; i <= n; i++) {
if (vis[i])
continue;
pri[np++] = i;
for (int j = i + i; j <= n; j += i)
vis[j] = 1;
}
}
Matrix A;
int solve (Matrix a, 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]) {
r = k;
break;
}
if (A[r][j]) {
if (r != i) {
for (k = 0; k <= n; k++)
swap(A[r][k], A[i][k]);
}
for (u = i + 1; u < m; u++) {
if (A[u][j])
for (k = i; k <= n; k++)
A[u][k] ^= A[i][k];
}
i++;
}
j++;
}
return i;
}
int main () {
prime_table(maxn);
int cas;
scanf("%d", &cas);
while (cas--) {
ll x;
int n, maxp = 0;
scanf("%d", &n);
memset(A, 0, sizeof(A));
for (int i = 0; i < n; i++) {
scanf("%lld", &x);
for (int j = 0; j < np; j++) {
while (x % pri[j] == 0) {
maxp = max(maxp, j);
x /= pri[j];
A[j][i] ^= 1;
}
}
}
int ret = solve(A, maxp+1, n);
printf("%lld\n", (1LL<<(n-ret))-1);
}
return 0;
}
分享到:
相关推荐
判断输入字符串是否为镜像或回文串。 来源于UVaOJ - 401. 水题。
开源项目-codingsince1985-UVa#uva-online-judge-solutions-in-golang.zip,两年来每天都在解决一个uva在线裁判问题,算起来…
uva705 Slash Maze 的代码,在UVaOJ上通过
PDF试题
uva532 Dungeon Master的源代码,并且AC了
Algorithm-UVA-Solutions-in-Python.zip,python 3中各种uva(acm)问题的解决方案。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
这是UVA133 TheDoleQueue救济金发放问题,经典的算法问题。初学算法的人要对这种算法非常熟悉并且能熟练运用。
tpcw-nyu-uva-client 客户端
leetcode 2 算法-Java UVa Online Judge(ACM-ICPC Live ...使用:数组、哈希表、链表、二分搜索、动态规划、堆栈、堆、reedy、排序、树 DFS、BFS、图、二分搜索树、递归、记忆、队列、映射等。...Uva-ACM-ICPC