hdu 5755 2016 Multi-University Training Contest 3 Gambler Bo 高斯消元模3同余方程

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

 #include<bits/stdc++.h>

 using namespace std;

 #define rep0(i,l,r) for(int i = (l);i < (r);i++)

 #define rep1(i,l,r) for(int i = (l);i <= (r);i++)

 #define rep_0(i,r,l) for(int i = (r);i > (l);i--)

 #define rep_1(i,r,l) for(int i = (r);i >= (l);i--)

 #define MS0(a) memset(a,0,sizeof(a))

 #define MS1(a) memset(a,-1,sizeof(a))

 #define MSi(a) memset(a,0x3f,sizeof(a))

 #define pb push_back

 #define A first

 #define B second

 #define MK make_pair

 #define inf 0x3f3f3f3f

 #define eps 1e-8

 #define zero(x) (((x)>0?(x):-(x))<eps)

 #define bitnum(a) __builtin_popcount(a)

 #define lowbit(x) (x&(-x))

 #define clear0 (0xFFFFFFFE)

 #define mod 3

 #define K(x) ((x)*(x))

 typedef pair<int,int> PII;

 typedef long long ll;

 typedef unsigned long long ull;

 template<typename T>

 void read1(T &m)

 {

     T x = ,f = ;char ch = getchar();

     while(ch <'' || ch >''){ if(ch == '-') f = -;ch=getchar(); }

     while(ch >= '' && ch <= ''){ x = x* + ch - '';ch = getchar(); }

     m = x*f;

 }

 template<typename T>

 void read2(T &a,T &b){read1(a);read1(b);}

 template<typename T>

 void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);}

 template<typename T>

 void out(T a)

 {

     if(a>) out(a/);

     putchar(a%+'');

 }

 inline ll gcd(ll a,ll b){ return b == ? a: gcd(b,a%b); }

 inline ll lcm(ll a,ll b){ return a/gcd(a,b)*b; }

 const int maxn = ;

 int a[maxn][maxn];

 int x[maxn<<];

 void init(int n,int m)

 {

     rep0(i,,n) rep0(j,,m){

         int t = i*m + j;

         a[t][t] = ;

         if(i > ) a[t - m][t] = ;

         if(i < n-) a[t + m][t] = ;

         if(j > ) a[t-][t] = ;

         if(j < m-) a[t+][t] = ;

     }

 }

 int equ, var;

 int Gauss()

 {

     int mx, row, col;

     for(row = , col = ; row < equ && col < var; row++, col++){

         mx = row;

         for(int i = row+;i < equ;i++){

             if(abs(a[i][col]) > abs(a[mx][col])) mx = i;

         }

         if(a[mx][col] == ) {

             row--;

             continue;

         }

         if(mx != row){

             for(int j = col;j < var + ;j++)

                 swap(a[row][j], a[mx][j]);

         }

         for(int i = row+;i < equ;i++){

             if(a[i][col]){

                 int LCM = lcm(abs(a[i][col]), abs(a[row][col]));

                 int ta = LCM/abs(a[i][col]), tb = LCM/abs(a[row][col]);

                 if(a[i][col] * a[row][col] < ) tb = -tb;

                 for(int j = col; j < var+;j++)

                     a[i][j] = ((a[i][j]*ta - a[row][j]*tb)%mod+mod)%mod;

             }

         }

     }

     for(int i = var-; i >= ; i--){

         if(a[i][i] == ) continue;

         int tmp = a[i][var];

         for(int j = i+;j < var;j++){

             if(a[i][j]){

                 tmp -= a[i][j]*x[j];

                 tmp = (tmp%mod + mod)% mod;

             }

         }

         x[i] = (tmp*a[i][i])% mod;

     }

     return ;

 }

 vector<int> vec;

 int main()

 {

     //freopen("data.txt","r",stdin);

     //freopen("out.txt","w",stdout);

     int T, kase = ;

     scanf("%d",&T);

     while(T--){

         int n, m, t;

         read2(n,m);

         equ = n*m, var = n*m;

         MS0(a);

         rep0(i,,n) rep0(j,,m) read1(t), a[i*m+j][var] = (mod-t)%mod;

         init(n,m);

         Gauss();

         vec.clear();

         rep0(i,,var)  while(x[i]--) vec.pb(i);

         out(vec.size());puts("");

         rep0(i,,vec.size()) printf("%d %d\n",vec[i]/m + , vec[i]%m + );

     }

     return ;

 }