POJ-3526, AOJ-1284 : The Teacher’s Side of Math

問題概要

t = a^(1/m) + b^(1/n) (a,bは異なる素数,n*m<20)を解に持つような整数係数の多項式で、次数最小で最高次の係数が1になるようなものを求める問題。そのような解が存在することが知られている。

解法

問題文にヒントが書いてあって答はn*m次の多項式になると決め打ちして良さげ。最高次以降の係数を変数にしてa^(i/m)*b^(j/n)の各係数が全て0になるよう連立一次方程式を立てる。これを整数の範囲で解くのだけど適当にdoubleで解いて丸めても無事通った。大きい数のmodで計算してもよいかもしれない。

acceptされたコード

int A, B, N, M;

bool init() {
	scanf("%d%d%d%d", &A, &N, &B, &M);
	return A > 0;
}

const int MAX_COMB = 30;
int64 comb[MAX_COMB + 1][MAX_COMB + 1];

inline int toIndex(int n, int m) {
	return n * M + m + 1;
}

void solve() {
	vector< vector<double> > mat(N*M + 1, vector<double>(N*M + 1, 0.0));
	vector<double> b(N*M + 1, 0.0);
	mat[0][0] = 1.0; b[0] = 1.0;
	for (int d = 0; d <= N*M; ++d) {
		for (int k = 0; k <= d; ++k) {
			int64 a = comb[d][k];
			a *= calcPow(A, k/N) * calcPow(B, (d-k)/M);
			mat[toIndex(k%N, (d-k)%M)][d < N*M ? d + 1 : 0] += a;
		}
	}

	vector<double> x = solveLinearEquations(mat, b);

	reverse(x.begin() + 1, x.end());
	for (int i = 0; i <= N*M; ++i) {
		printf("%d%c", int(round(x[i])), i == N*M ? '\n': ' ');
	}
}

int main() {
	buildCombination();
	for (;init();) {
		solve();
	}
	return 0;
}