同余意义下的高斯消元法
以下高斯消元指的是列主元高斯消元法。
高斯消元法除了解浮点数线性方程，它还可以用于求矩阵的秩，求某些线性空间中的一组线性无关的基，解同余方程组。
求秩
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;
}
|
|
收藏
淘帖
踩
