UVA11524构造系数数组+高斯消元解异或方程组-白红宇

UVA11524构造系数数组+高斯消元解异或方程组

阅读量：5049 次

发布时间：2019-06-12

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

1 /*UVA11524  2 题目：给定n个数(n<=100)，从中找出1或多个数，使他们的乘积是一个完全平方数  3 分析：转化成数理模型是第一步，肯定要分解质因数，ps：题目给定不含大于500的素因子。  4 第二选择的数字相同质因子个数之和必须是偶数，因为之奇偶性有关，可将奇数为1，偶数为0，这样约简。  5 然后按照常理，应该找出所有的可能性（暴力的思想），因为n<=100，不可能用状态压缩的办法，所以用下面的方法，同时也是给自己一个拓展的思路  6 高斯消元解异或方程组：  7 假设n个数，设数组ch[i]，表式选第i的数与否，那么，列出每个质因子的总个数方程，总个数模2为0即可，因为异或等同于模2加，故列异或方程。  8 最后自由变量假设有k个，则说明2^k-1种方案  9 解异或方程组的思路： 10 1、构造系数数组（0,1） 11 Mat[i][j]:第i个质因数的方程，第j个数字的因数分解后的个数 12 2、解异或方程Mat(n,m)//要收录 13  14 int solve(int n1,int m1) //解方程部分借鉴白书，要弄明白 15 { 16     int i=0,j=0; 17     while(i
     
      
        39 #include
       
         40 #include
        
          41 #include
         
           42 #include
          
            43 #include
           
             44 #include
            
              45 #include
             
               46 #include
               47 //#define LL long long 48 using namespace std; 49 50 bool isprim[505]; 51 int cnt; 52 int prim[505/2]; 53 void prime_calc() 54 { 55 cnt=0; 56 memset(isprim,0,sizeof(isprim)); 57 for(int i=2; i<=500; i++) 58 { 59 if (!isprim[i]) 60 { 61 prim[cnt++]=i; 62 for(int j=2*i; j<=500; j+=i) isprim[j]=1; 63 } 64 } 65 } 66 67 int T,n; 68 int A[505][505]; 69 70 int solve(int n1,int m1) //解方程部分借鉴白书，要弄明白 71 { 72 int i=0,j=0; 73 while(i
               
                
                 >T; 98 // cout<
                 
                  <
                  
                   >n;102 int n1=0,m1=n;103 memset(A,0,sizeof(A));104 long long k;105 for(int i=0; i
                   
                    >k;108 for(int j=0; j