Gauss 消元（模板）

/* 
    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==-1)
        {
            printf("no answer
");
            return 0; 
         } 
        if(p==-2)
        { 
               printf("have float answer
");
            return 0; 
        }
        printf("the num of free_x is %d
",p);
        print(m);
    }
    return 0;
}
//输出解的和,自由变元数量以及各个解 
void print(int n)
{
    //    若有小数解换为xd输出 
    int sum=0;
    for(int i=0;i<n;i++)
        sum+=x[i];
    printf("sum=%d
",sum); 
    for(int i=0;i<n;i++)
        printf("x%d=%d
",i+1,x[i]);
    return ;
}
//读入增广矩阵 
void init(int n,int m)
{
    clr(A);
    for(int i=0;i<n;i++)
        for(int j=0;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=0,max_r,dou,max_x,LCM,ta,tb;
//k为当前操作行，col为操作主元素所在列 
    for(k=0,col=0;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+1;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]==0)
        {
            k--;
            free_x[num++]=col;
            //自由变元为当前col 
            continue;
        }
        for(int i=k+1;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]<0) 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]!=0)
            return -1;    
    int temp;
    //对自由变元的赋值，可有多种方式 
    //若为小数解则换为xd; 
    for(int i=0;i<num;i++)
        x[free_x[i]]=0;
    //int  xi,yi; exgcd需要 
    for(int i=k-1,c=m-1;i>=0;c=m-1,i--)
    {
        temp=A[i][m];
        while(x[c]!=-1)
        {
            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]!=0) return -2;
        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==0)
    {
        x=1;
        y=0;
        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!=0)
    {
        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 = 1000003;
const int N =2e2+10;
LL A[N][N];
LL a[N];
LL MOD(LL x){
    return (x%mod+mod)%mod;
}
LL qpow(LL x,LL n){
    LL res = 1;
    for(;n;n>>=1,x = MOD(x*x))
        if(n&1) res = MOD(res*x);
    return res;
}
int gauss(int n){
    LL d;
    int col = n;
    bool flag;
    for(int i=0;i<n;i++){
        if(A[i][i] == 0){
            flag = 0;
            for(int j=i+1;j<n;j++){
                if(A[j][i] != 0 ){
                    for(int k=i;k<=n;k++)
                        swap(A[j][k],A[i][k]);
                    flag = 1;
                    break;
                }
            }
            if(!flag){
                col--;
                continue;
            }
        }
        d = qpow(A[i][i],mod-2);
        for(int j=i;j<=n;j++)

            A[i][j] = MOD(A[i][j] * d);
        for(int j=0;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(0);
    cout.tie(0);
    LL x;
    LL d;
    for(int i=0;i<=10;i++){
        cout<<"? "<<i<<endl;
        fflush(stdout);
        cin>>x;
        for(int j=0;j<=10;j++)
            A[i][j] = qpow(i,j);
        A[i][11] = x;
    }
    gauss(11);
    for(int i=0;i<=10;i++)
        a[i] = A[i][11];
    LL ans = -1;
    for(int i=0;i<mod;i++)
    {
        x = 0;
        for(int j = 10;j>=0;j--)
            x = MOD(MOD(x * i) + a[j]);
        if(x == 0)
            ans = i;
    }
    cout<<"! "<<ans<<endl;
}