Codeforces #453 Div1 B. GCD of Polynomials

少し手間取ったけどまぁどうにか。
http://codeforces.com/contest/901/problem/B

問題

正整数Nが与えられる。
N次以下の多項式のうち、以下を満たす対を求めよ。

• 最大次数の係数は1
• 各係数は整数で、絶対値は1以下
• ユークリッドの互除法を適用すると、N回除算ができる

解法

N次多項式と(N-1)次多項式を並べて、剰余を取るたびに大きい方の次数が2下がるようにしよう。
そのようなxのN次多項式をf(N,x)とする。
f(N,x)をf(N-1,x)で割った余りがf(N-2,x)になればいいので、f(N,x)をf(N-1,x)のx倍とf(N-2)を適当に加減算して生成し、絶対値が1を超えないようにしよう。

int N;

int A[160][160];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	A[0][0]=1;
	A[1][1]=-1;
	for(i=2;i<=152;i++) {
		FOR(j,153) {
			if(j) A[i][j]=-A[i-1][j-1];
		}
		int pl=1,mi=1;
		FOR(j,153) {
			if(abs(A[i][j]+A[i-2][j])>=2) pl=0;
			if(abs(A[i][j]-A[i-2][j])>=2) mi=0;
		}
		assert(pl||mi);
		FOR(j,153) {
			if(pl) A[i][j]+=A[i-2][j];
			else A[i][j]-=A[i-2][j];
		}
	}
	
	FOR(i,152) {
		if(A[i][i]<0) {
			FOR(j,152) A[i][j]=-A[i][j];
		}
	}
	
	cin>>N;
	_P("%d\n",N);
	FOR(i,N+1) _P("%d%c",A[N][i],(i==N)?'\n':' ');
	N--;
	_P("%d\n",N);
	FOR(i,N+1) _P("%d%c",A[N][i],(i==N)?'\n':' ');
	
}

まとめ

Advent Calendarが終わったので、少し時間ができました。