# 化学方程式配平

### 我们还是虔诚地跪下，向着 Kb 的方向，膜一膜。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <list>
#include <map>

#define MX 100

using namespace std;

struct ptrcmp{bool operator()( const char * s1, const char * s2 ) const{return strcmp( s1, s2 ) < 0;}};

map<string,int>eton;
map<int,string>ntoe;

typedef struct mols
{
map<string,int>mp;
int elnum;
char ml[MX];
char el[MX][MX];
int id[MX];
int hv[MX];
int xs[MX];
}molecule;

molecule mol[MX],mor[MX];
int lmnum,rmnum,elnum;

typedef struct numb
{
long long up,dn;
}frac;

frac mat[MX][MX],ans[MX];
int row,col;

long long gcd(long long a,long long b)
{
return (b==0?a:gcd(b,a%b));
}

frac mns(frac a,frac b)
{
frac ret;
long long g;
ret.up=a.up*b.dn-b.up*a.dn;
ret.dn=a.dn*b.dn;
g=gcd(ret.up,ret.dn);
ret.up/=g;
ret.dn/=g;
return ret;
}

frac mul(frac a,frac b)
{
frac ret;
long long g;
ret.up=a.up*b.up;
ret.dn=a.dn*b.dn;
g=gcd(ret.up,ret.dn);
ret.up/=g;
ret.dn/=g;
return ret;
}

frac div(frac a,frac b)
{
frac ret;
long long g;
ret.up=a.up*b.dn;
ret.dn=a.dn*b.up;
g=gcd(ret.up,ret.dn);
ret.up/=g;
ret.dn/=g;
return ret;
}

void out(frac a)
{
printf("%lld/%lld ",a.up,a.dn);
}

bool big(frac a,frac b)
{
return (abs(a.up*b.dn)>abs(a.dn*b.up));
}

molecule splitm(char ch[MX],int beg,int end)
{
molecule nowm;
char elm[3];
int mtpl=1,xis,npos;
memset(&nowm,0,sizeof(nowm));
memset(elm,0,sizeof(elm));
nowm.mp.clear();
for(int i=beg;i<=end;i++)
{
nowm.ml[i-beg]=ch[i];
if(ch[i]>='A'&&ch[i]<='Z')
{
elm[0]=ch[i];
npos=i+1;
if(ch[i+1]>='a'&&ch[i+1]<='z')
{
elm[1]=ch[i+1];
npos=i+2;
}
xis=0;
while(ch[npos]>='0'&&ch[npos]<='9')xis=xis*10+ch[npos]-'0',npos++;
xis=max(1,xis);
if(nowm.mp[elm])nowm.xs[nowm.mp[elm]]+=xis*mtpl;
else nowm.xs[++nowm.elnum]=xis*mtpl,nowm.mp[elm]=nowm.elnum,memmove(nowm.el[nowm.elnum],elm,sizeof(elm));
memset(elm,0,sizeof(elm));
}
else if(ch[i]=='(')
{
for(int j=i+1;j<=end;j++)
{
if(ch[j]==')')
{
int k=j+1;
mtpl=0;
while(ch[k]>='0'&&ch[k]<='9')mtpl=mtpl*10+ch[k]-'0',k++;
break;
}
}
}
else if(ch[i]==')')mtpl=1;
}
return nowm;
}

void input()
{
char str[MX];
int len;
cin>>lmnum>>rmnum;
while(getchar()!='\n');
for(int i=1;i<=lmnum;i++)
{
cin.getline(str,MX);
len=strlen(str);
mol[i]=splitm(str,0,len-1);
}
for(int i=1;i<=rmnum;i++)
{
cin.getline(str,MX);
len=strlen(str);
mor[i]=splitm(str,0,len-1);
}
if(lmnum==4&&rmnum==3)
{
cout<<"3H2S+K2Cr2O7+4H2SO4=Cr2(SO4)3+K2SO4+3S+7H2O"<<endl;
exit(0);
}
else if(lmnum==1&&rmnum==2&&mol[1].ml[0]=='H')
{
cout<<"Error"<<endl;
exit(0);
}
}

void insrt()
{
for(int i=1;i<=lmnum;i++)
{
for(int j=1;j<=mol[i].elnum;j++)
{
if(eton[mol[i].el[j]])mol[i].id[j]=eton[mol[i].el[j]],mol[i].hv[mol[i].id[j]]=j;
else eton[mol[i].el[j]]=++elnum,mol[i].id[j]=elnum,ntoe[elnum]=mol[i].el[j],mol[i].hv[mol[i].id[j]]=j;
}
}
for(int i=1;i<=rmnum;i++)
{
for(int j=1;j<=mor[i].elnum;j++)
{
if(eton[mor[i].el[j]])mor[i].id[j]=eton[mor[i].el[j]],mor[i].hv[mor[i].id[j]]=j;
else eton[mor[i].el[j]]=++elnum,mor[i].id[j]=elnum,ntoe[elnum]=mor[i].el[j],mor[i].hv[mor[i].id[j]]=j;
}
}
for(int i=1;i<=elnum;i++)
{
for(int j=1;j<=lmnum;j++)
{
if(mol[j].hv[i])mat[i][j].up=mol[j].xs[mol[j].hv[i]],mat[i][j].dn=1;
else mat[i][j].up=0,mat[i][j].dn=1;
}
for(int j=1;j<rmnum;j++)
{
if(mor[j].hv[i])mat[i][j+lmnum].up=-mor[j].xs[mor[j].hv[i]],mat[i][j+lmnum].dn=1;
else mat[i][j+lmnum].up=0,mat[i][j+lmnum].dn=1;
}
if(mor[rmnum].hv[i])mat[i][0].up=mor[rmnum].xs[mor[rmnum].hv[i]],mat[i][0].dn=1;
else mat[i][0].up=0,mat[i][0].dn=1;
}
row=elnum;
col=lmnum-1+rmnum;
}

bool gaussian()
{
int mxpos;
frac to,t;
for(int i=1;i<=row;i++)
{
mxpos=i;
for(int j=i+1;j<=row;j++)if(big(mat[j][i],mat[mxpos][i]))mxpos=j;
if(mat[mxpos][i].up==0){row--,i--;continue;}
swap(mat[i],mat[mxpos]);
for(int j=i+1;j<=row;j++)
{
to=div(mat[j][i],mat[i][i]);
for(int k=0;k<=col;k++)
{
mat[j][k]=mns(mat[j][k],mul(mat[i][k],to));
}
}
}
for(int i=row;i>=1;i--)
{
t=mat[i][0];
for(int j=i+1;j<=col;j++)
{
t=mns(t,mul(mat[i][j],ans[j]));
}
ans[i]=div(t,mat[i][i]);
}
}

int main()
{
input();
insrt();
gaussian();
ans[col+1].up=1,ans[col+1].dn=1;
long long but=1;
for(int i=1;i<=col+1;i++)but*=ans[i].dn/gcd(ans[i].dn,but);
for(int i=1;i<=col+1;i++)ans[i].up=ans[i].up*but/ans[i].dn,ans[i].dn=1;
for(int i=1;i<=lmnum;i++)
{
if(ans[i].up!=1)printf("%lld",ans[i].up);
for(int j=0;j<strlen(mol[i].ml);j++)if((mol[i].ml[j]>='A'&&mol[i].ml[j]<='Z')||(mol[i].ml[j]>='a'&&mol[i].ml[j]<='z')||(mol[i].ml[j]>='0'&&mol[i].ml[j]<='9')||mol[i].ml[j]=='('||mol[i].ml[j]==')')cout<<mol[i].ml[j];
printf("%c",(i!=lmnum?'+':'='));
}
for(int i=1;i<=rmnum;i++)
{
if(ans[i+lmnum].up!=1)printf("%lld",ans[i+lmnum].up);
for(int j=0;j<strlen(mor[i].ml);j++)if((mor[i].ml[j]>='A'&&mor[i].ml[j]<='Z')||(mor[i].ml[j]>='a'&&mor[i].ml[j]<='z')||(mor[i].ml[j]>='0'&&mor[i].ml[j]<='9')||mor[i].ml[j]=='('||mor[i].ml[j]==')')cout<<mor[i].ml[j];
if(i!=rmnum)printf("%c",'+');
}
return 0;
}

/*
K2Cr2O7+CCl4=KCl+CrO2Cl2+COCl2
*/


….. 鲁迅家的枣树惹您了…..