AOJ 1293 Common Polynomial

問題

xの多項式が二つ与えられる。
二つの式の最大公約数を求めよ。

制約条件

次数は10以下。係数は100以下。
普通に解くと32bit整数でオーバーフローしない。

方針

構文解析して式を読み込む。
式を読んだら、整数の互除法と同じように式で互除法をすればいい。

互除法したら、式を出力する。
x^1の項とx^0の項だけ出力の形式に注意する。

ソースコード

いつもの我流の変なO(n^2)ではなく、O(n)の構文解析。

vi normalize(vi a){
	while(a.size() && a.back() == 0) a.pop_back();
	if(a.empty()) return a;
	ll g = a.back();
	rep(i, a.size()) g = __gcd(g, a[i]);
	if(g) rep(i, a.size()) a[i] /= g;
	if(a.back() < 0) rep(i, a.size()) a[i] *= -1;
	return a;
}
vi operator+(vi a, vi b){
	while(a.size() < b.size()) a.pb(0);
	rep(i, b.size()) a[i] += b[i];
	return a;
}
vi operator*(vi a, vi b){
	vi res(a.size() + b.size() - 1);
	rep(i, a.size()) rep(j, b.size())
		res[i+j] += a[i] * b[j];
	return res;
}
void out(vi v){
	reverse(all(v));
	int n = v.size();
	bool f = 1;
	rep(i, n) if(v[i]){
		if(!f || v[i] < 0) cout << (v[i] > 0 ? "+" : "-");
		f = 0;
		if(i == n-1 || abs(v[i]) != 1) cout << abs(v[i]);
		if(i < n-1) cout << "x";
		if(i < n-2) cout << "^" << n-i-1;
	}
	cout << endl;
}

ll number();
vi primary(), factor(), term(), expr();

string in;
int p;

ll number(){
	ll n = 0;
	for(; p < in.size() && isdigit(in[p]); p++) n *= 10, n += in[p] - '0';
	return n;
}
vi primary(){
	if(in[p] == 'x'){
		p++;
		vi res(2); res[1] = 1;
		return res;
	}
	if(isdigit(in[p])){
		return vi(1, number());
	}
	p++;
	vi res(expr());
	p++;
	return res;
}
vi factor(){
	vi tmp(primary()), res(1, 1);
	ll n = 1;
	if(p < in.size() && in[p] == '^'){
		p++; n = number();
	}
	rep(i, n) res = res * tmp;
	return res;
}
vi term(){
	bool minus = 0;
	if(in[p] == '+' || in[p] == '-'){
		if(in[p] == '-') minus = 1;
		p++;
	}
	vi res(1, 1);
	while(p < in.size() && in[p] != '+' && in[p] != '-' && in[p] != ')'){
		vi tmp(factor());
		res = res * tmp;
	}
	if(minus) rep(i, res.size()) res[i] *= -1;
	return res;
}
vi expr(){
	vi res(1, 0);
	while(p < in.size() && in[p] != ')'){
		vi tmp(term());
		res = res + tmp;
	}
	return res;
}

vi operator%(vi a, vi b){
	a = normalize(a); b = normalize(b);
	while(a.size() >= b.size()){
		int n = a.size(), m = b.size();
		ll g = __gcd(abs(a.back()), abs(b.back()));
		ll m1 = b.back() / g;
		rep(i, a.size()) a[i] *= m1;
		ll d = a.back() / b.back();
		rep(i, b.size()) a[i + a.size() - b.size()] -= b[i] * d;
		while(a.size() && a.back() == 0) a.pop_back();
	}
	return normalize(a);
}
vi gcd(vi a, vi b){
	if(b.empty()) return normalize(a);
	return gcd(b, a % b);
}

int main()
{
	while(getline(cin, in), in != "."){
		p = 0;
		vi a(expr());
		getline(cin, in);
		p = 0;
		vi b(expr());
		vi g(gcd(a, b));
		out(g);
	}
	
	return 0;
}