POJ 1166The Clocks 高斯消元 + exgcd(纯属瞎搞)

依据题意可构造出方程组。方程组的每一个方程格式均为：C1*x1 + C2*x2 + ...... + C9*x9 = sum + 4*ki;

高斯消元构造上三角矩阵，以最后一个一行为例：

C*x9 = sum + 4*k。exgcd求出符合范围的x9，其它方程在代入已知的变量后格式亦如此。

第一发Gauss。蛮激动的。

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <queue>

#include <cmath>

#include <stack>

#include <map>

#include <ctime>

#pragma comment(linker, "/STACK:1024000000");

#define EPS (1e-8)

#define LL long long

#define ULL unsigned long long

#define _LL __int64

#define INF 0x3f3f3f3f

#define Mod 6000007

using namespace std;

const int MAXN = 20;

int up[] = {0,4,3,4,3,5,3,4,3,4};

int site[10][5] = {

{0},

{1,2,4,5},

{1,2,3},

{2,3,5,6},

{1,4,7},

{2,4,5,6,8},

{3,6,9},

{4,5,7,8},

{7,8,9},

{5,6,8,9}

};

int Map[10];

LL coe[MAXN][MAXN];

LL sol[MAXN];

void Output()

{

    int i,j;

    for(i = 1;i <= 9; ++i)

    {

        for(j = 1;j <= 10; ++j)

        {

            printf("%lld ",coe[i][j]);

            if(j == 9)

                printf("= ");

        }

        printf("\n");

    }

    puts("");

}

LL Abs(LL x)

{

    if(x < 0)

        return -x;

    return x;

}

LL gcd(LL x,LL y)

{

    if(y == 0)

        return x;

    return gcd(y,x%y);

}

void exgcd(LL a,LL b,LL &x,LL &y)

{

    if(b == 0)

        x = 1,y = 0;

    else

    {

        LL x1,y1;

        exgcd(b,a%b,x1,y1);

        x = y1;

        y = x1-a/b*y1;

    }

}

//n为行数，m为列数(包括最后一项)

//return -1无整数解 return 0存在整数解。

int Gauss(int n,int m)

{

    int i,j,k;

    LL T,A,B;

    //Output();

    for(i = 1;i < n; ++i)

    {

        for(j = i+1;j <= n; ++j)

        {

            if(coe[j][i] == 0)

                continue;

            if(coe[i][i] == 0)

            {

                for(k = i;k <= m; ++k)

                    T = coe[i][k],coe[i][k] = coe[j][k],coe[j][k] = T;

                continue;

            }

            T = gcd(coe[i][i],coe[j][i]);

            A = coe[j][i]/T,B = coe[i][i]/T;

            for(k = i;k <= m; ++k)

                coe[j][k] = coe[i][k]*A - coe[j][k]*B;

        }

        //Output();

    }

    LL sum = 0;

    for(i = n;i >= 1; --i)

    {

        sum = coe[i][m];

        for(j = m-1;j > i; --j)

            sum -= coe[i][j]*sol[j];

        LL A = coe[i][i],B = 4,C = sum;

        LL x,y;

        exgcd(A,B,x,y);

        //cout<<"A = "<<A<<" B = "<<B<<" C = "<<C<<" x = "<<x<<" y = "<<y<<endl;

        x *= C/gcd(A,B);

        //cout<<"x = "<<x<<endl;

        y = B/gcd(A,B);

        x = (x-x/y*y + Abs(y))%Abs(y);

        sol[i] = x;

        //cout<<"i = "<<i<<" x = "<<x<<endl;

//        if(sum%coe[i][i] != 0)

//            return -1;//此时无整数解

//        sol[i] = sum/coe[i][i];

    }

    return 0;

}

int main()

{

    int i,j;

    for(i = 1;i <= 9; ++i)

        scanf("%d",&Map[i]);

    memset(coe,0,sizeof(coe));

    for(i = 1;i <= 9; ++i)

    {

        for(j = 0;j < up[i]; ++j)

        {

            coe[site[i][j]][i] = 1;

        }

    }

    for(i = 1;i <= 9; ++i)

        coe[i][10] = (4-Map[i])%4;

    if(-1 == Gauss(9,10))

        while(0)

        ;

    bool mark = true;

    for(i = 1;i <= 9;++i)

    {

        for(j = 0;j < sol[i]; ++j)

        {

            if(mark == false)

                printf(" ");

            else

                mark = false;

            printf("%d",i);

        }

    }

    return 0;

}