いろいろあわせ技。問題文が複雑だけど(というか英語読んでないんだけど)どうやら、
・方程式を解けばちゃんと解は一意になる(rankあまる)
・オーバーフローは、long longを使いつつそのつどgcdで割ったら問題ない
ということらしい。
ということで構文解析して有理数で方程式解いてうまく復元しておしまい。
大変。構文解析は普通に逆からやったほうがよかった気がする。
#include<stdio.h> #include<algorithm> #include<vector> using namespace std; const double EPS=1e-8; long long gcd(long long a,long long b){ while(b){ a%=b;long long c=a;a=b;b=c; } return a; } long long lcm(long long a,long long b){ return a/gcd(a,b)*b; } struct wolf{ long long bs,bb; wolf(){bs=0;bb=1;} wolf(long long a,long long b){ bs=a;bb=b; } wolf operator*(wolf a)const{long long BS=bs*a.bs;long long BB=bb*a.bb;long long G=gcd(BS,BB);return wolf(BS/G,BB/G);} wolf operator/(wolf a)const{long long BS=bs*a.bb;long long BB=bb*a.bs;long long G=gcd(BS,BB);return wolf(BS/G,BB/G);} wolf operator+(wolf a)const{long long nbb=lcm(bb,a.bb); long long BS=nbb/bb*bs+nbb/a.bb*a.bs;long long BB=nbb;long long G=gcd(BS,BB);return wolf(BS/G,BB/G);} wolf operator-(wolf a)const{long long nbb=lcm(bb,a.bb); long long BS=nbb/bb*bs-nbb/a.bb*a.bs;long long BB=nbb;long long G=gcd(BS,BB);return wolf(BS/G,BB/G);} wolf operator-()const{return wolf(-bs,bb);} }; typedef vector<wolf>vec; typedef vector<vec>mat; vec gauss_jordan(const mat &A,const vec &b){ int n=A.size(); int m=A[0].size(); //printf("%d %d\n",n,m); mat B(n,vec(m+1)); for(int i=0;i<n;i++) for(int j=0;j<m;j++)B[i][j]=A[i][j]; for(int i=0;i<n;i++)B[i][m]=b[i]; for(int i=0;i<m;i++){ int pivot=i; for(int j=i;j<n;j++){ if(B[j][i].bs)pivot=j; } swap(B[i],B[pivot]); if(!B[i][i].bs)continue; for(int j=i+1;j<=m;j++)B[i][j]=B[i][j]/B[i][i]; for(int j=0;j<n;j++){ if(i!=j){ for(int k=i+1;k<=m;k++)B[j][k]=B[j][k]-B[j][i]*B[i][k]; } } } vec x(m); for(int i=0;i<m;i++)x[i]=B[i][m]; // for(int i=0;i<m;i++)printf("(%lld/%lld) ",x[i].bs,x[i].bb); // printf("\n"); return x; } char str[1100]; int cur; bool neg; int at=0; int v=0; int num[70000]; bool ch(char t){ if('A'<=t&&t<='Z')return true; if('a'<=t&&t<='z')return true; if('0'<=t&&t<='9')return true; if(t=='('||t==')')return true; return false; } int s[100][100]; void term(){ bool nes=false; int fi=cur; while(ch(str[cur])){ cur++; } int ks1=1; int ks2=1; for(int i=cur-1;i>=fi;i--){ if('0'<=str[i]&&str[i]<='9'){ int kk=1; int kt=0; while('0'<=str[i]&&str[i]<='9'){ kt+=(str[i]-'0')*kk; kk*=10; i--; } i++; if(nes)ks2=kt; else ks1=kt; continue; } if(str[i]==')'){ nes=true;continue; } if(str[i]=='('){ ks1=1; nes=false;continue; } if('a'<=str[i]&&str[i]<='z'){ int val=(int)str[i-1]*256+str[i]; int to; if(~num[val])to=num[val]; else to=num[val]=v++; if(neg)s[at][to]-=ks1*ks2; else s[at][to]+=ks1*ks2; if(nes)ks2=1; else ks1=1; i--; continue; } int val=str[i]; int to; if(~num[val])to=num[val]; else to=num[val]=v++; if(neg)s[at][to]-=ks1*ks2; else s[at][to]+=ks1*ks2; if(nes)ks2=1; else ks1=1; continue; } } void expr(){ term();at++; while(str[cur]=='+'){ cur++; term();at++; } } long long ret[100]; int main(){ while(1){ scanf("%s",str); if(str[0]=='.')return 0; for(int i=0;i<100;i++)for(int j=0;j<100;j++)s[i][j]=0; for(int i=0;i<70000;i++)num[i]=-1; cur=0; at=0;v=0; neg=false; expr(); cur+=2; neg=true; expr(); mat A(v+1,vec(at)); vec B(v+1,wolf()); for(int i=0;i<v;i++){ for(int j=0;j<at;j++)A[i][j]=wolf(s[j][i],1); } A[v][0]=wolf(1,1); B[v]=wolf(1,1); // for(int i=0;i<v+1;i++){ // for(int j=0;j<at;j++)printf("%lld ",A[i][j].bs); // printf("\n"); // } // printf("in\n"); vec x=gauss_jordan(A,B); for(int i=0;i<x.size();i++)if(x[i].bb<0){ x[i].bb=-x[i].bb; x[i].bs=-x[i].bs; } // for(int i=0;i<x.size();i++)printf("(%lld/%lld) ",x[i].bs,x[i].bb); // printf("\n"); // printf("out\n");fflush(stdout); long long t=1; for(int i=0;i<at;i++)t=lcm(t,x[i].bb); for(int i=0;i<at;i++)ret[i]=t/x[i].bb*x[i].bs; long long g=ret[0]; for(int i=0;i<at;i++)g=gcd(g,ret[i]); for(int i=0;i<at;i++)ret[i]/=g; for(int i=0;i<at;i++){ if(i)printf(" "); printf("%lld",ret[i]); } printf("\n"); } }
