This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1293 #include<bits/stdc++.h> using namespace std; #define call_from_test #include "../../polynomial/polynomial.cpp" #undef call_from_test using P = Polynomial<int>; P expr(string s,int &p); P factor(string s,int &p); P term(string s,int &p); int number(string s,int &p); P expr(string s,int &p){ P res; if(s[p]=='-'){ p++; res=-factor(s,p); }else res=factor(s,p); while(p<(int)s.size()){ if(s[p]=='+'){ p++; res=res+factor(s,p); continue; } if(s[p]=='-'){ p++; res=res-factor(s,p); continue; } break; } return res; } P factor(string s,int &p){ P res=term(s,p); while(p<(int)s.size()){ if(s[p]=='+') break; if(s[p]=='-') break; if(s[p]==')') break; res=res*term(s,p); } return res; } P term(string s,int &p){ if(s[p]=='('){ p++; P res=expr(s,p); assert(s[p]==')'); p++; if(s[p]=='^'){ p++; int k=number(s,p); res=res.pow(res,k); } return res; } int v=(s[p]=='x'?1:number(s,p)); if(p<(int)s.size()&&s[p]=='x'){ p++; if(p<(int)s.size()&&s[p]=='^'){ p++; int k=number(s,p); P res(k+1); res[k]=v; return res; } P res(2); res[1]=v; return res; } P res; res[0]=v; return res; } int number(string s,int &p){ int res=0; while(p<(int)s.size()&&isdigit(s[p])) res=res*10+(s[p++]-'0'); return res; } P calc(string s){ int p=0; return expr(s,p); } signed main(){ string s,t; while(cin>>s,s!="."){ cin>>t; P ps=calc(s); P pt=calc(t); P ans=gcd(ps,pt); ans.print(); } return 0; }
#line 1 "test/aoj/1293.test.cpp" // verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1293 #include<bits/stdc++.h> using namespace std; #define call_from_test #line 1 "polynomial/polynomial.cpp" #line 3 "polynomial/polynomial.cpp" using namespace std; #endif //BEGIN CUT HERE template<typename T> struct Polynomial{ using P = Polynomial; vector<T> co; Polynomial():co(1,T(1)){} Polynomial(int sz):co(sz,0){} Polynomial(vector<T> co):co(co){} size_t size() const{ return co.size(); }; void shrink(){ while(co.size()>1u and !co.back()) co.pop_back(); } void reduce(){ T g=abs(co.back()); if(!g) return; for(T c:co) if(c!=0) g=__gcd(g,abs(c)); if(co.back()<0) g*=-1; for(T &c:co) c/=g; } void print(){ shrink(); reduce(); int n=size(),flg=0; for(int i=n-1;i>0;i--){ if(!co[i]) continue; flg=1; if(i!=n-1 and co[i]>0) cout<<"+"; if(co[i]==-1) cout<<"-"; else if(co[i]!=1) cout<<co[i]; cout<<"x"; if(i!=1) cout<<"^"<<i; } if(co[0]){ if(flg and co[0]>0) cout<<"+"; cout<<co[0]; } cout<<endl; } T operator[](int i) const{ return co[i]; } T &operator[](int i){ return co[i]; } P operator-() const{ P res=*this; for(T &c:res.co) c*=-1; return res; } P operator+(const P &a) const{ int n=size(),m=a.size(); P res(max(n,m)); for(int i=0;i<n;i++) res[i]+=co[i]; for(int i=0;i<m;i++) res[i]+=a[i]; return res; } P operator-(const P &a) const{return *this+(-a);}; P operator*(const P &a) const{ int n=size(),m=a.size(); P res(n+m); for(int i=0;i<n;i++) for(int j=0;j<m;j++) res[i+j]+=co[i]*a[j]; res.shrink(); return res; } P pow(const P &a,int k) const{ P res; for(int i=0;i<k;i++) res=res*a; return res; } pair<P, P> divide(const P &a) const{ int n=size(),m=a.size(),s=n-m+1; if(s<0) return make_pair(P(1),*this); P div(s); P rest=*this; for(int i=0;i<s;i++){ if(rest[n-(i+1)]%a[m-1]!=0) for(T &c:rest.co) c*=a[m-1]; T d=rest[n-(i+1)]/a[m-1]; div[s-(i+1)]=d; for(int j=m;j>0;j--) rest[n-(i+j)]-=a[m-j]*d; } return make_pair(div,rest); } P operator/(const P &a) const{return divide(a).first;}; P operator%(const P &a) const{return divide(a).second;}; }; template<typename T> Polynomial<T> gcd(Polynomial<T> a,Polynomial<T> b){ a.shrink();a.reduce(); b.shrink();b.reduce(); if(a.size()<b.size()) swap(a,b); if(b.size()==1u and !b[0]) return a; return gcd(b,a%b); } //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE signed main(){ return 0; } #endif #line 8 "test/aoj/1293.test.cpp" #undef call_from_test using P = Polynomial<int>; P expr(string s,int &p); P factor(string s,int &p); P term(string s,int &p); int number(string s,int &p); P expr(string s,int &p){ P res; if(s[p]=='-'){ p++; res=-factor(s,p); }else res=factor(s,p); while(p<(int)s.size()){ if(s[p]=='+'){ p++; res=res+factor(s,p); continue; } if(s[p]=='-'){ p++; res=res-factor(s,p); continue; } break; } return res; } P factor(string s,int &p){ P res=term(s,p); while(p<(int)s.size()){ if(s[p]=='+') break; if(s[p]=='-') break; if(s[p]==')') break; res=res*term(s,p); } return res; } P term(string s,int &p){ if(s[p]=='('){ p++; P res=expr(s,p); assert(s[p]==')'); p++; if(s[p]=='^'){ p++; int k=number(s,p); res=res.pow(res,k); } return res; } int v=(s[p]=='x'?1:number(s,p)); if(p<(int)s.size()&&s[p]=='x'){ p++; if(p<(int)s.size()&&s[p]=='^'){ p++; int k=number(s,p); P res(k+1); res[k]=v; return res; } P res(2); res[1]=v; return res; } P res; res[0]=v; return res; } int number(string s,int &p){ int res=0; while(p<(int)s.size()&&isdigit(s[p])) res=res*10+(s[p++]-'0'); return res; } P calc(string s){ int p=0; return expr(s,p); } signed main(){ string s,t; while(cin>>s,s!="."){ cin>>t; P ps=calc(s); P pt=calc(t); P ans=gcd(ps,pt); ans.print(); } return 0; }