题目链接

http://acm.sgu.ru/problem.php?contest=0&problem=200

题目大意

给出m个整理,因子全部为前t个素数。问有多少个子集,乘积是平方数。

题解

列方程组,a1, a2, a3 ……, am分别表示bi是否在集合中。对于每一个素因子,建立异或方程组,要求因子个数为偶数,即异或为0,也可以做模2运算。子集个数便是解的个数,高斯消元后求出变元个数num,结果是2^num - 1。

此题需要用到高精度。

代码

//
//  main.cpp
//  sgu
// 
//  Site @haipz.com
//  Copyright (c) 2015年 林海鸿. All rights reserved.
//

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <iostream>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 105;

int prime[MAXN];
int f[MAXN];

void mult(int *a, int b) {
    for (int i = 1; i <= a[0]; ++i) a[i] *= b;
    for (int i = 1; i < a[0]; ++i) {
        a[i + 1] += a[i]/10;
        a[i] %= 10;
    }
    while (a[a[0]] >= 10) {
        a[a[0] + 1] = a[a[0]]/10;
        a[a[0]++] %= 10;
    }
    return;
}

void sub(int *a, int b) {
    a[1] -= b;
    for (int i = 1; i < a[0]; ++i)
        while (a[i] < 0) {
            a[i] += 10;
            --a[i + 1];
        }
    while (a[0] > 1 && a[a[0]] == 0) --a[0];
    return;
}

bool isPrime(int n) {
    for (int i = 2; i*i <= n; ++i)
        if (n % i == 0) return false;
    return true;
}

// row为当前行
// col为当前列
// free_num为自由元数
// a为推广矩阵
// x为唯一解
// free_x为自由元行
int a[MAXN][MAXN], x[MAXN], free_x[MAXN];
int Gauss(int equ, int var) {
    int row, col, free_num = 0;
    for (row = 0, col = 0; row < equ && col < var; ++row, ++col) {
        int max_r = row;
        for (int i = row + 1 ; i < equ; ++i)
            if(abs(a[i][col]) > abs(a[max_r][col])) max_r = i; // 找到当前列最小行
        if (a[max_r][col] == 0) { // 如果未找到则为一自由元
            --row;
            free_x[free_num++] = col;
            continue;
        }
        if (max_r != row) // 最小行不为当前行则交换
            for(int j = col; j < var + 1; ++j)
                swap(a[row][j], a[max_r][j]);
        for (int i = row + 1; i < equ; i++) // 对其余行进行运算
            if (a[i][col] != 0)
                for (int j = col; j < var + 1; ++j)
                    a[i][j] ^= a[row][j];
    }
    for (int i = row; i < equ; ++i) // 如果剩余行非零则无解
        if (a[i][col] != 0) return -1;
    if (row < var) return var - row; // 多解则返回自由元个数
    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 main() {
    int cur = 2, num = 0;
    while (num < MAXN) {
        if (isPrime(cur)) prime[num++] = cur;
        ++cur;
    }
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        memset(a, 0, sizeof(a));
        for (int i = 0; i < m; ++i) {
            int t;
            scanf("%d", &t);
            for (int j = 0; j < n; ++j)
                while (t % prime[j] == 0) {
                    a[j][i] ^= 1;
                    t /= prime[j];
                }
        }
        int res = Gauss(n, m);
        f[0] = f[1] = 1;
        for (int i = 0; i < res; ++i) mult(f, 2);
        sub(f, 1);
        for (int i = f[0]; i >= 1; --i) printf("%d", f[i]);
        printf("\n");
    }
    return 0;
}

转载保留版权:http://haipz.com/blog/i/6470 - 海胖博客