hdu 5833 Zhu and 772002 ccpc网络赛高斯消元法-白红宇

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

阅读量：4480 次

发布时间：2019-06-08

本文共 2498 字，大约阅读时间需要 8 分钟。

传送门：

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

思路：

小于等于2000的素数一共也只有305个

一个数，如果他某个素数因子的幂为偶，那这个素数的可以不用考虑；如果幂为奇数，那这个素数就应当被考虑如何与其他数凑成幂为偶数。例如12，可以表示为2^2*3,2的幂次为2,3的幂次为1，所以，如果要和其他数相乘为完全平方数，那么一定要与素数因子3为奇次的合并

那么根据上面两条，我们可以列出方程：x1*a11+x2*a12+...+xn*a1n=0；x为解，如果aii取为1，不取为0；aii表示ai的第i个素数因子是否为奇，是为1，否则为0，(素数按从小到大排序，依次为2,3,5,7...)

答案即为2^（x中自由元的个数）-1

/**************************************************************    Problem:hdu 5833 Zhu and 772002    User: youmi    Language: C++    Result: Accepted    Time:    Memory:****************************************************************///#pragma comment(linker, "/STACK:1024000000,1024000000")//#include
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #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<<"*************************"<
                   
                     inline void read(T &n){ char c; int flag = 1; for (c = getchar(); !(c >= '0' && c <= '9' || c == '-'); c = getchar()); if (c == '-') flag = -1, n = 0; else n = c - '0'; for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) n = n * 10 + c - '0'; n *= flag;}ll Pow(ll base, ll n, ll mo){ if (n == 0) return 1; if (n == 1) return base % mo; ll tmp = Pow(base, n >> 1, mo); tmp = (ll)tmp * tmp % mo; if (n & 1) tmp = (ll)tmp * base % mo; return tmp;}//***************************int n;const ll mod=1000000007;const int maxn=50010;ll prime[maxn];bool isprime[maxn*20];int tot;int a[400][400];int x[400];int fre[400];int index;int tt=305;void prim()//素数筛法{ tot=0; memset(isprime,true,sizeof(isprime)); prime[tot++]=2; for(int i=3;i
                    
                     abs(a[mx][j])) mx=k; } if(mx!=i) { for(k=j;k
                     
                      =0;k--) { int num=0; for(int t=0;t
                      
                       1) continue; int temp=a[k][cl-1]; for(int t=0;t
                       
                        <= T;kase++) { int n; scanf("%d", &n); zeros(a); zeros(x); memset(fre,1,sizeof(fre)); for (int i=0;i