【高斯消元】3道例题

03 Sep 2016

这3道题在VJ上都可以找到，我就不放题目链接了。还有最近HDU怎么老炸…

【UVA 11542】Square

题目大意

给你n个数字，要你从中间选出若干个数，使得他们的乘积为一个平方数。问你有多少种不同的选法。（不能一个数都不选）

题解

这一题是白书上的例题，很经典。我们设\(x_i=0\)时第i个数不选，\(x_i=1\)时选。那么我们就可以把最终的乘积表示出来： \[ {p_i}^{x_i·…·x_j}·{p_j}^{…}… \]

这个表示可能有些奇怪，其中\(p_i\)是某个质因数，而\(p_i\)的指数则是含有这个质因数的数所对应的\(x_i\)，我们知道如果一个数是平方数的话他的指数必须是一个偶数。所以我们可以根据这个列出一个异或方程组，然后利用高斯消元求出自由变元的个数就行了。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#define LL long long
#define maxn 105

using namespace std;

int T,n,pri[505],cnt,A[505][maxn];
LL a[maxn];
bool vis[505];

void setup(int high)
{
    cnt=0;
    memset(vis,0,sizeof(vis));
    memset(pri,0,sizeof(pri));
    for (int i=2;i<=high;i++)
    {
        if (!vis[i])
        {
            pri[cnt++]=i;
            vis[i]=1;
        }
        for (int j=0;j<cnt && pri[j]*i<=high;j++)
        {
            vis[i*pri[j]]=1;
            if (i%pri[j]==0) break;
        }
    }
}

int solve(int n,int m)
{
    int i=0,j=0;
    while (i<n && j<m)
    {
        for (int k=i;k<n;k++) if (A[k][j])
        {
            if (k!=i) for (int p=0;p<m;p++) swap(A[i][p],A[k][p]);
            break;
        }
        if (A[i][j])
        {
            for (int k=i+1;k<n;k++) if (A[k][j])
                for (int p=0;p<m;p++) if (A[i][p]) A[k][p]^=A[i][p];
            i++;
        }
        j++;
    }
    return i;
}

int main()
{
    setup(500);
    scanf("%d",&T);
    while (T--)
    {
        memset(A,0,sizeof(A));
        memset(a,0,sizeof(a));
        int m=0;
        scanf("%d",&n);
        for (int i=0;i<n;i++) scanf("%lld",&a[i]);
        for (int i=0;i<n;i++)
            for (int j=0;j<cnt && pri[j]<=a[i];j++)
            while (a[i]%pri[j]==0)
        {
            m=max(m,j);
            a[i]/=pri[j];
            A[j][i]^=1;
        }
        int ans=solve(m+1,n);
        printf("%lld\n",(1LL <<(n-ans))-1);
    }
    return 0;
}

【POJ 1830】开关问题

题目大意

现在有若干个开关，每个开关只有两种状态，每个开关只能被操作一次，但是有些开关是会互相影响的，问你是否能达到最终状态。

题解

这个其实跟上面那题挺像的，也是对每个开关建立方程，最后高斯消元求解即可。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#define LL long long
#define maxn 35

using namespace std;

int T,a[maxn],b[maxn],n,A[maxn][maxn];

int solve(int n)
{
    int i=0,j=0;
    while (i<n && j<n)
    {
        for (int k=i;k<n;k++) if (A[k][j])
        {
            if (k!=i) for (int p=0;p<=n;p++) swap(A[k][p],A[i][p]);
            break;
        }
        if (A[i][j])
        {
            for (int k=i+1;k<n;k++) if (A[k][j])
                for (int p=0;p<=n;p++) A[k][p]^=A[i][p];
            i++;
        }
        j++;
    }
    for (int k=i;k<n;k++) if (A[k][n]) return -1;
    return i;
}

int main()
{
    scanf("%d",&T);
    while (T--)
    {
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(A,0,sizeof(A));
        scanf("%d",&n);
        for (int i=0;i<n;i++) scanf("%d",&a[i]);
        for (int i=0;i<n;i++)
        {
            scanf("%d",&b[i]);
            if (a[i]) b[i]^=1;
        }
        int c,d;
        while (scanf("%d%d",&c,&d),c!=0 || d!=0)
        {
            A[d-1][c-1]=1;
        }
        for (int i=0;i<n;i++) A[i][i]=1;
        for (int i=0;i<n;i++) A[i][n]=b[i];
        int C=solve(n);
        LL ans=(1LL<<(n-C));
        if (C==-1 || ans==0) printf("Oh,it's impossible~!!\n");
        else printf("%lld\n",ans);
    }
    return 0;
}

【POJ 1222】EXTENDED LIGHTS OUT

题目大意兼题解

这题其实就是把互相影响的开关变成了互相影响的方块，同样也是对每个方块建立方程，然后求解。

注意最后的回代过程，容易求错。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#define LL long long

using namespace std;

int T,a[10][10],A[35][35];

void solve(int n)
{
    int i=1,j=1;
    while (i<=n && j<=n)
    {
        for (int k=i;k<=n;k++) if (A[k][j])
        {
            if (k!=i) for (int p=1;p<=n+1;p++) swap(A[k][p],A[i][p]);
            break;
        }
        if (A[i][j])
        {
            for (int k=i+1;k<=n;k++) if (A[k][j])
                for (int p=j;p<=n+1;p++) A[k][p]^=A[i][p];
            i++;
        }
        j++;
    }
    for (int i=n;i>=1;i--)
        for (int j=i+1;j<=n;j++) A[i][n+1]^=(A[j][n+1] && A[i][j]);
}

int main()
{
    int Case=1;
    scanf("%d",&T);
    while (T--)
    {
        memset(a,0,sizeof(a));
        memset(A,0,sizeof(A));
        for (int i=0;i<5;i++)
            for (int j=0;j<6;j++)
            {
                scanf("%d",&a[i][j]);
                A[j+1+i*6][31]=a[i][j];
            }
        for (int i=1;i<=30;i++)
        {
            A[i][i]=1;
            if (i-6>=1) A[i][i-6]=1;
            if (i+6<=30) A[i][i+6]=1;
            if ((i-1)%6!=0) A[i][i-1]=1;
            if ((i+1)%6!=1) A[i][i+1]=1;
        }
        solve(30);
        printf("PUZZLE #%d\n",Case++);
        for (int i=1;i<=30;i++)
            if (i%6==0) printf("%d\n",A[i][31]);
            else printf("%d ",A[i][31]);
    }
    return 0;
}

ACM 数学高斯消元