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; }