hdu 5833 Zhu and 772002 ccpc网络赛 高斯消元法

时间：2023-03-08 16:41:17

传送门：hdu 5833 Zhu and 772002

题意：给n个数，每个数的素数因子不大于2000，让你从其中选则大于等于1个数相乘之后的结果为完全平方数

思路：

  1. 小于等于2000的素数一共也只有305个
  2. 一个数，如果他某个素数因子的幂为偶，那这个素数的可以不用考虑；如果幂为奇数，那这个素数就应当被考虑如何与其他数凑成幂为偶数。例如12，可以表示为2^2*3,2的幂次为2,3的幂次为1，所以，如果要和其他数相乘为完全平方数，那么一定要与素数因子3为奇次的合并
  3. 那么根据上面两条，我们可以列出方程：x1*a11+x2*a12+...+xn*a1n=0；x为解，如果aii取为1，不取为0；aii表示ai的第i个素数因子是否为奇，是为1，否则为0，(素数按从小到大排序，依次为2,3,5,7...)
  4. 答案即为2^（x中*元的个数）-1
/**************************************************************

    Problem:hdu 5833 Zhu and 772002

    User: youmi

    Language: C++

    Result: Accepted

    Time:

    Memory:

****************************************************************/

//#pragma comment(linker, "/STACK:1024000000,1024000000")

//#include<bits/stdc++.h>

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <map>

#include <stack>

#include <set>

#include <sstream>

#include <cmath>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#define zeros(a) memset(a,0,sizeof(a))

#define ones(a) memset(a,-1,sizeof(a))

#define sc(a) scanf("%d",&a)

#define sc2(a,b) scanf("%d%d",&a,&b)

#define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c)

#define scs(a) scanf("%s",a)

#define sclld(a) scanf("%I64d",&a)

#define pt(a) printf("%d\n",a)

#define ptlld(a) printf("%I64d\n",a)

#define rep(i,from,to) for(int i=from;i<=to;i++)

#define irep(i,to,from) for(int i=to;i>=from;i--)

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

#define lson (step<<1)

#define rson (lson+1)

#define eps 1e-6

#define oo 0x3fffffff

#define TEST cout<<"*************************"<<endl

const double pi=*atan(1.0);

using namespace std;

typedef long long ll;

template <class T> inline void read(T &n)

{

    char c; int flag = ;

    for (c = getchar(); !(c >= '' && c <= '' || c == '-'); c = getchar()); if (c == '-') flag = -, n = ; else n = c - '';

    for (c = getchar(); c >= '' && c <= ''; c = getchar()) n = n *  + c - ''; n *= flag;

}

ll Pow(ll base, ll n, ll mo)

{

    if (n == ) return ;

    if (n == ) return base % mo;

    ll tmp = Pow(base, n >> , mo);

    tmp = (ll)tmp * tmp % mo;

    if (n & ) tmp = (ll)tmp * base % mo;

    return tmp;

}

//***************************

int n;

const ll mod=;

const int maxn=;

ll prime[maxn];

bool isprime[maxn*];

int tot;

int a[][];

int x[];

int fre[];

int index;

int tt=;

void prim()//素数筛法

{

    tot=;

    memset(isprime,true,sizeof(isprime));

    prime[tot++]=;

    for(int i=;i<maxn;i+=)

    {

        if(isprime[i])

        {

            prime[tot++]=i;

            for(ll j=i;1ll*i*j<1ll*maxn;j+=)

                isprime[i*j]=false;

        }

    }

}

void solve(int i,ll x)//判断x有哪些素数因子的幂为奇

{

    int cnt=;

    rep(j,,tot)

    {

        cnt=;

        if(x%prime[j]==)

        {

            while(x%prime[j]==)

            {

                cnt++;

                x/=prime[j];

            }

        }

        if(cnt%)

            a[i][j]=;

        if(x==)

            break;

    }

}

void debug(int rw,int cl)

{

    rep(i,,rw-)

    {

        rep(j,,cl-)

            printf("%d ",a[i][j]);

        printf("\n");

    }

}

int gauss(int rw,int cl)//高斯消元法，01异或

{

    int i,j,k;

    int mx=;

    for(i=,j=;i<rw&&j<cl-;i++,j++)

    {

        mx=i;

        for(k=i;k<rw;k++)

        {

            if(abs(a[k][j])>abs(a[mx][j]))

                mx=k;

        }

        if(mx!=i)

        {

            for(k=j;k<cl;k++)

                swap(a[mx][k],a[i][k]);

        }

        if(a[i][j]==)

        {

            i--;

            continue;

        }

        for(k=i+;k<rw;k++)

        {

            if(a[k][j]!=)

            {

                for(int t=j;t<cl;t++)

                {

                    a[k][t]^=a[i][t];

                }

            }

        }

    }

    if(i<rw)

    {

        for(k=i-;k>=;k--)

        {

            int num=;

            for(int t=;t<cl;t++)

            {

                if(a[k][t]!=&&fre[t])

                    num++,index=t;

            }

            if(num>)

                continue;

            int temp=a[k][cl-];

            for(int t=;t<cl-;t++)

                if(a[k][t]!=&&index!=t)

                    temp^=a[k][t]&&x[t];

            x[k]=temp&&a[k][k];

            fre[index]=;

        }

        return rw-i;

    }

    return ;

}

int main()

{

    #ifndef ONLINE_JUDGE

    freopen("in.txt","r",stdin);

    #endif

    prim();

    int T;

    scanf("%d", &T);

    for (int kase = ;kase <= T;kase++)

    {

        int n;

        scanf("%d", &n);

        zeros(a);

        zeros(x);

        memset(fre,,sizeof(fre));

        for (int i=;i<n;i++)

        {

            long long x;

            scanf("%I64d", &x);

            solve(i,x);

        }

        ll ans=gauss(n,tt);

        ans=(Pow(,ans,mod)-+mod)%mod;

        printf("Case #%d:\n%I64d\n", kase,ans);

    }

    return ;

}

相关文章