/*
title：Gauss消元整数解/小数解整数矩阵模板
author：lhk
time: 2016.9.11
没学vim的菜鸡自己手打了
*/
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define clr(x) memset(x,0,sizeof(x))
#define clrdown(x) memset(x,-1,sizeof(x))
#define maxn 910
#define maxm 910
#define mod 3
using namespace std;
int A[maxn][maxm];//Gauss消元的增广矩阵
int free_x[maxm];//自由变元的位置
int x[maxm];//整数解集
double xd[maxm];//小数解集
void init(int n,int m);//矩阵初始化操作
int gauss(int n,int m);//gauss消元部分
void print(int n);//输出解集
int exgcd(int a,int b,int &x,int &y);//扩展欧几里得求逆元,对于模mod的矩阵除法需要
int lcm(int a,int b);
int gcd(int a,int b);
int main()
{
int T,n,m;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
init(n,m);
int p=gauss(n,m);
if(p==-)
{
printf("no answer\n");
return ;
}
if(p==-)
{
printf("have float answer\n");
return ;
}
printf("the num of free_x is %d\n",p);
print(m);
}
return ;
}
//输出解的和,自由变元数量以及各个解
void print(int n)
{
// 若有小数解换为xd输出
int sum=;
for(int i=;i<n;i++)
sum+=x[i];
printf("sum=%d\n",sum);
for(int i=;i<n;i++)
printf("x%d=%d\n",i+,x[i]);
return ;
}
//读入增广矩阵
void init(int n,int m)
{
clr(A);
for(int i=;i<n;i++)
for(int j=;j<=m;j++)
scanf("%d",&A[i][j]);
clrdown(x);
clr(free_x);
return ;
}
int gauss(int n,int m)//输出-1是无解，-2是有小数解，>=0则是自由变元的数量和全为整数解
{
int k,col,num=,max_r,dou,max_x,LCM,ta,tb;
//k为当前操作行，col为操作主元素所在列
for(k=,col=;k<n && col<m;k++,col++)
{
//若A[K][col]不为col列最大，则将k行与k+1到n-1行中A[i][col]绝对值最大的行交换
max_r=k;
max_x=abs(A[k][col]);
for(int i=k+;i<n;i++)
if(max_x<abs(A[i][col]))
{
max_x=abs(A[i][col]);
max_r=i;
}
if(max_r!=k)
{
for(int j=col;j<=m;j++)
swap(A[k][j],A[max_r][j]);
}
//若k到n-1行A[i][col]全为0,则主元素指向当前行下一列的元素
if(A[k][col]==)
{
k--;
free_x[num++]=col;
//自由变元为当前col
continue;
}
for(int i=k+;i<n;i++)
if(A[i][col])
{
LCM=lcm(abs(A[k][col]),abs(A[i][col]));
ta=LCM/abs(A[i][col]);
tb=LCM/abs(A[k][col]);
if(A[k][col]*A[i][col]<) tb=-tb;//若符号不同则取反
for(int j=col;j<=m;j++)
{
A[i][j]=A[i][j]*ta-A[k][j]*tb;
// A[i][j]=((A[i][j]*ta-A[k][j]*tb)%mod+mod)%mod; //模mod矩阵的消元
}
}
}
//k行及之后若有(0,0,0……,0,a)(a!=0）的行，则无解输出-1
for(int i=k;i<n;i++)
if(A[i][col]!=)
return -;
int temp;
//对自由变元的赋值，可有多种方式
//若为小数解则换为xd;
for(int i=;i<num;i++)
x[free_x[i]]=;
//int xi,yi; exgcd需要
for(int i=k-,c=m-;i>=;c=m-,i--)
{
temp=A[i][m];
while(x[c]!=-)
{
if(A[i][c])
temp-=x[c]*A[i][c];
//temp=((temp-(x[c]*A[i][c])%mod)%mod+mod)%mod;//模mod矩阵的回代
c--;
}
if(temp%A[i][c]!=) return -;
x[c]=temp/A[i][c];
/*exgcd(A[i][c],mod,xi,yi);
xi=(xi%mod+mod)%mod;
x[c]=(temp*xi%mod+mod)%mod;*/ //模mod 矩阵的x[i]的赋值
}
return col-k;
}
int exgcd(int a,int b,int &x,int &y)
{
if(b==)
{
x=;
y=;
return a;
}
else
{
int r=exgcd(b,a%b,y,x);
y-=x*(a/b);
return r;
}
}
int gcd(int a,int b)
{
int c;
while(b!=)
{
c=a%b;
a=b;
b=c;
}
return a;
}
int lcm(int a,int b)
{
return a/gcd(a,b)*b;
}
Educational Codeforces Round 63 (Rated for Div. 2) F
https://codeforces.com/contest/1155/problem/F
#include<bits/stdc++.h>
#define clr(x) memset(x,0,sizeof(x))
#define cpy(x,y) memcpy(y,x,sizeof(x))
#define INF 0x3f3f3f3f
#define LL long long
#define fi first
#define se second
#define pb push_back
using namespace std;
const LL mod = ;
const int N =2e2+;
LL A[N][N];
LL a[N];
LL MOD(LL x){
return (x%mod+mod)%mod;
}
LL qpow(LL x,LL n){
LL res = ;
for(;n;n>>=,x = MOD(x*x))
if(n&) res = MOD(res*x);
return res;
}
int gauss(int n){
LL d;
int col = n;
bool flag;
for(int i=;i<n;i++){
if(A[i][i] == ){
flag = ;
for(int j=i+;j<n;j++){
if(A[j][i] != ){
for(int k=i;k<=n;k++)
swap(A[j][k],A[i][k]);
flag = ;
break;
}
}
if(!flag){
col--;
continue;
}
}
d = qpow(A[i][i],mod-);
for(int j=i;j<=n;j++) A[i][j] = MOD(A[i][j] * d);
for(int j=;j<n;j++){
if(i!=j){
d = A[j][i];
for(int k=i;k<=n;k++){
A[j][k] = MOD(A[j][k] - MOD(d * A[i][k]));
}
}
}
}
return col;
}
int main(){
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
LL x;
LL d;
for(int i=;i<=;i++){
cout<<"? "<<i<<endl;
fflush(stdout);
cin>>x;
for(int j=;j<=;j++)
A[i][j] = qpow(i,j);
A[i][] = x;
}
gauss();
for(int i=;i<=;i++)
a[i] = A[i][];
LL ans = -;
for(int i=;i<mod;i++)
{
x = ;
for(int j = ;j>=;j--)
x = MOD(MOD(x * i) + a[j]);
if(x == )
ans = i;
}
cout<<"! "<<ans<<endl;
}