同余意义下的高斯消元Python解决几类常见的问题+例题【黑马python培训】

更新时间:2019年07月26日 10时50分35秒来源:黑马程序员论坛

同余意义下的高斯消元法
以下高斯消元指的是列主元高斯消元法。

高斯消元法除了解浮点数线性方程，它还可以用于求矩阵的秩，求某些线性空间中的一组线性无关的基，解同余方程组。

求秩
SGU 200 Cracking RSA
题意：给你m个正的整型数，这m个数的质因子仅来自前t个质数，求它们能组成多少完全平方数。（每个数最多选一次，且不能一个数都不选）
Sample test(s)
Input
(t=)3 (m=)4
9 20 500 3
Output
3
Sample 解释： 9 = 3 ^ 2, 20 * 500 = 100 ^ 2 , 9 * 20 * 500 = 300 ^ 2是完全平方数，其余均不是。
思路：
首先可以现将它们分解，事实上，3 ^ 1 和 3 ^ 3从某种意义是一样的，因为完全平方数要求所有的不同种类质因子的个数是偶数。于是就可以用二元域来表示。
如上面的例子
2 3 5
9 0 0 0
20 0 0 1
500 0 0 1

几个数能组成完成平方数就等价于它在这样的矩阵表示中的行向量相加（二元域的加法，即异或运算）等于一个 0 向量。用高斯消元的思想化解为标准阶梯型矩阵，并且求出矩阵的秩r，并且有一定有r<=t，并且原矩阵和当前的标准阶梯型矩阵是等价的，也就是所原先m个数，与现在经过高斯消元后的新的数是完全等价的。由于每一个数，只能选取一次，而如果选择了行向量表示中非零向量的元素又行向量已经是线性无关的，则一定不能构成零向量，即完全平方数。所以要组成完成平方数就只能在行向量表示中为零向量的元素选，这样的元素总有（m-r）个，每一元素选择选或者不选，但不能全不选，所以答案就是2 ^ （m-r ） -1 。
举上面的例题为例，消元之后变为
2 3 5
20 0 0 1
9 0 0 0
1000 0 0 0

这个矩阵的秩为1，行向量表示中为零向量的元素总有（3-1）个，所以答案为2 ^（3-1）-1。
当然这道题的 m - r 最大可能等于100，即所给的数都是完全平方数，这时已经2 ^ （m-r ） -1 已经超出了long long的范围，需要手写大整数，至于求 2 ^ （m-r ） -1，再使用快速幂运算即可求出。

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <stack>
#include <vector>
#include <string.h>
#include <queue>
#define msc(X) memset(X,-1,sizeof(X))
#define ms(X) memset(X,0,sizeof(X))
typedef long long LL;
using namespace std;
const int MAXN=1300;
bool Isn_Prime[MAXN+5];
int prime[230];
void GetPrime(void)
{
ms(Isn_Prime);
prime[0]=0;
for(int i=2;i<=MAXN;i++)
{
      if(!Isn_Prime[i]) prime[++prime[0]]=i;
      for(int j=1;j<=prime[0]&&prime[j]<=MAXN/i;j++)
      {
         Isn_Prime[prime[j]*i]=true;
         if(i%prime[j]==0) break;
      }
}
}
int m,t;
int a[105][105];
int Guass(void)
{
int max_r,col,k;
for(k=col=0;k<m&&col<t;k++,col++)
{
      max_r=k;
      for(int i=k+1;i<m;i++)
         if(abs(a[i][col])>abs(a[max_r][col]))
            max_r=i;
      if(a[max_r][col]==0){
         k--;continue;
      }
      if(max_r!=k){
         for(int j=col;j<t;j++)
            swap(a[k][j],a[max_r][j]);
      }
      for(int i=k+1;i<m;i++)
         if(a[i][col]){
            for(int j=col;j<t;j++)
                  a[i][j]^=https://www.smpeizi.com/swap/a[k][j];
         }
}
return m-k;
}
struct BigInt
{
const static int mod=10000;
const static int DLEN=4;
int a[600],len;
BigInt(void){
      ms(a);
      len=1;
}
BigInt(int v){
      ms(a);
      len=0;
      do{
         a[len++]=v%mod;
         v/=mod;
      }while(v);
}
BigInt operator +(const BigInt &b)const {
      BigInt res;
      res.len=max(len,b.len);
      for(int i=0;i<=res.len;i++)
         res.a[i]=0;
      for(int i=0;i<res.len;i++)
      {
         res.a[i]+=((i<len)?a[i]:0)+((i<b.len)?b.a[i]:0);
         res.a[i+1]+=https://www.pzzs168.com/ res.len/res.a[i]/mod;
         res.a[i]%=mod;
      }
      if(res.a[res.len]>0) res.len++;
      return res;
}
BigInt operator *(const BigInt &b)const {
      BigInt res;
      for(int i=0;i<len;i++)
      {
         int up=0;
         for(int j=0;j<b.len;j++)
         {
            int tmp=a[i]*b.a[j]+res.a[i+j]+up;
            res.a[i+j]=tmp%mod;
            up=tmp/mod;
         }
         if(up)
            res.a[i+b.len]=up;
      }
      res.len=len+b.len;
      while(res.a[res.len-1]==0&&res.len>1)
         res.len--;
      return res;
}
void output(void)
{
      printf("%d",a[len-1] );
      for(int i=len-2;i>=0;i--)
         printf("%04d",a[i] );
      putchar('\n');
}
};
BigInt quick_pow(int k)
{
BigInt a=BigInt(2),
res=BigInt(1);
while(k){
      if(k&1) res=res*a;
      k>>=1;
      a=a*a;
}
return res+BigInt(-1);
}
int main(int argc, char const *argv[])
{
GetPrime();
while(scanf("%d %d",&t,&m)==2){
      ms(a);
      for(int i=0;i<m;i++)
      {
         int tmp;
         scanf("%d",&tmp);
         for(int j=0;j<t;j++)
            while(tmp%prime[j+1]==0)
            {
                  tmp/=https://www.idiancai.com/ms/prime[j+1];
                  a[i][j]^=1;
            }
      }
      BigInt rs=quick_pow(Guass());
      rs.output();
}
return 0;

求基
Xor
比如这么一道题，求一组最小的基
Xor
题意：xor运算符是一种二进制运算，对于两个整数a,b，如果c=a xor b，那么c二进制表示的每一位的值由a二进制表示和b二进制表示的相应位进行不进位加法得到，例如1 xor 1=0,1 xor 0 =1。
现在给出 n个数，那么用xor运算符可以得到很多不同的值，现在问第几小的数？
Example
2
1 2
那么由1,2这两个数进行xor运算可以得到3个数 1,2,3.

对于这道题，我们可以将这些数用二进制写出来
2 ^ 0 2 ^ 1 2 ^ 2
1 1 0 0
2 0 1 0
3 1 1 0
4 0 0 1
显然3可以由1 xor 2得到，也就是1,2,3他们是线性相关的，
所以我们应该对这n个数张成的空间求出一组线性无关的基，又由于求的是第几小，所以希望每个数消元后的数都尽量小，所以应该从高位开始消元进行消元。
当然，这里的消元用的是高斯消元的那种思想，没必要把整个矩阵弄出来。
如果这道题求的是第k大，其实可以转化为第几小，应该如果求出来它的秩是n，那么总共可以组成2^n-1个数，那么其实就是第2^n-k小。

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <stack>
#include <vector>
#include <string.h>
#include <queue>
#define msc(X) memset(X,-1,sizeof(X))
#define ms(X) memset(X,0,sizeof(X))
typedef long long LL;
using namespace std;
LL a[10005];
int n;
//求第几小应该从最高位开始消元，这样保证了线性无关组元素和最小
void Guass(void)
{
int max_r,col,k;
for(k=0,col=60;k<n&&col>=0;col--)
{
      max_r=https://www.aiidol.com/LL/k;
      for(int i=k+1;i<n;i++)
         if(a[i]&(1ll<<col)) {
            max_r=i;
            break;
         }
      if((a[max_r]&(1ll<<col))==0)
         continue;
      if(max_r!=k)
         swap(a[k],a[max_r]);
      for(int i=0;i<n;i++)
         if(i!=k&&(a[i]&(1ll<<col)))
            a[i]^=a[k];
      k++;
}
sort(a,a+n);
n=unique(a,a+n)-a;
}
LL cal(LL k)
{
LL ans=0;
int i=0;
if(a[0]==0){
      if(k==1) return 0;
      k--;
      i++;
}
for(;i<n&&k;k>>=1,i++)
      if(k&1)
         ans^=a[i];
if(i==n&&k) return -1;
return ans;
}
int main(int argc, char const *argv[])
{
int t,ti=0;
scanf("%d",&t);
while(++ti<=t){
      scanf("%d",&n);
      for(int i=0;i<n;i++)
         scanf("%I64d",a+i);
      Guass();
      printf("Case #%d:\n",ti);
      int q;
      scanf("%d",&q);
      while(q--){
         LL k;
         scanf("%I64d",&k);
         printf("%I64d\n",cal(k) );
      }
}
return 0;
}

推荐了解热门学科

java培训	Python人工智能	Web前端培训	PHP培训
区块链培训	影视制作培训	C++培训	产品经理培训
UI设计培训	新媒体培训	产品经理培训	Linux运维
大数据培训	智能机器人软件开发

传智播客是一家致力于培养高素质软件开发人才的科技公司，“黑马程序员”是传智播客旗下高端IT教育品牌。自“黑马程序员”成立以来，教学研发团队一直致力于打造精品课程资源，不断在产、学、研3个层面创新自己的执教理念与教学方针，并集中“黑马程序员”的优势力量，针对性地出版了计算机系列教材50多册，制作教学视频数+套，发表各类技术文章数百篇。

传智播客从未停止思考

传智播客副总裁毕向东在2019IT培训行业变革大会提到，“传智播客意识到企业的用人需求已经从初级程序员升级到中高级程序员，具备多领域、多行业项目经验的人才成为企业用人的首选。”

中级程序员和初级程序员的差别在哪里?
项目经验。毕向东表示，“中级程序员和初级程序员最大的差别在于中级程序员比初级程序员多了三四年的工作经验，从而多出了更多的项目经验。“为此，传智播客研究院引进曾在知名IT企业如阿里、IBM就职的高级技术专家，集中研发面向中高级程序员的课程，用以满足企业用人需求，尽快补全IT行业所需的人才缺口。

何为中高级程序员课程?

传智播客进行了定义。中高级程序员课程，是在当前主流的初级程序员课程的基础上，增加多领域多行业的含金量项目，从技术的广度和深度上进行拓展。“我们希望用5年的时间，打造上百个高含金量的项目，覆盖主流的32个行业。”传智播客课程研发总监于洋表示。

黑马程序员热门视频教程【点击播放】

Python入门教程完整版（懂中文就能学会）	零起点打开Java世界的大门
C++\| 匠心之作从0到1入门学编程	PHP\|零基础入门开发者编程核心技术
Web前端入门教程_Web前端html+css+JavaScript	软件测试入门到精通

上海中心

同余意义下的高斯消元Python解决几类常见的问题+例题【黑马python培训】

相关阅读