题目链接：https://vjudge.net/problem/POJ-2947
题意：转换题意后就是已知m个同余方程，求n个变量。
思路：
值得学习的是这个模板里消元用到lcm的那一块。注意题目输出的答案在[3,9]之间。
AC代码：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std; const int maxn=;
int n,m,a[maxn][maxn],x[maxn];
char s1[],s2[]; int gcd(int a,int b){
return b?gcd(b,a%b):a;
} int lcm(int a,int b){
return a/gcd(a,b)*b; //先除后乘
} // 高斯消元法解方程组(Gauss-Jordan elimination).(
//-1表示无解，0表示唯一解，大于0表示无穷解，并返回自由变元的个数)
//有equ个方程，var个变元。增广矩阵行数为equ,分别为0到equ-1,列数为var+1,分别为0到var.
int Gauss(int equ,int var){
int k,max_r,col=,ta,tb,LCM,temp;
for(int i=;i<var;++i){
x[i]=;
}
for(k=;k<equ&&col<var;++k,++col){
max_r=k;
//找系数绝对值最大的那一行与第k行交换
for(int i=k+;i<equ;++i){
if(abs(a[i][col])>abs(a[max_r][col]))
max_r=i;
}
if(max_r!=k){
for(int i=col;i<var+;++i)
swap(a[max_r][i],a[k][i]);
}
if(!a[k][col]){
--k;
continue;
}
for(int i=k+;i<equ;++i){
if(!a[i][col]) continue;
LCM=lcm(abs(a[i][col]),abs(a[k][col]));
ta=LCM/abs(a[i][col]);
tb=LCM/abs(a[k][col]);
if(a[i][col]*a[k][col]<) tb=-tb; //异号的情况是相加
for(int j=col;j<var+;++j){
a[i][j]=((a[i][j]*ta-a[k][j]*tb)%+)%;
}
}
}
//无解的情况
for(int i=k;i<equ;++i){
if(a[i][col]) return -;
}
//无穷解的情况
if(k<var){
return var-k; //返回自由变元的个数
}
//唯一解的情况，增广矩阵中形成严格的上三角阵
for(int i=var-;i>=;--i){
temp=a[i][var];
for(int j=i+;j<var;++j){
if(!a[i][j]) continue;
temp-=a[i][j]*x[j];
temp=(temp%+)%;
}
while(temp%a[i][i]!=) temp+=;
x[i]=(temp/a[i][i])%;
}
return ;
} int tran(char *s){
if(strcmp(s,"MON")==) return ;
else if(strcmp(s,"TUE")==) return ;
else if(strcmp(s,"WED")==) return ;
else if(strcmp(s,"THU")==) return ;
else if(strcmp(s,"FRI")==) return ;
else if(strcmp(s,"SAT")==) return ;
else return ;
} int main(){
while(scanf("%d%d",&n,&m),n||m){
memset(a,,sizeof(a));
for(int i=;i<m;++i){
int k;
scanf("%d%s%s",&k,s1,s2);
a[i][n]=((tran(s2)-tran(s1)+)%+)%;
while(k--){
int t;
scanf("%d",&t);
--t;
++a[i][t];
a[i][t]%=;
}
}
int ans=Gauss(m,n);
if(ans==){
for(int i=;i<n;++i)
if(x[i]<=) x[i]+=;
for(int i=;i<n-;++i)
printf("%d ",x[i]);
printf("%d\n",x[n-]);
}
else if(ans==-){
printf("Inconsistent data.\n");
}
else{
printf("Multiple solutions.\n");
}
}
return ;
}