POJ 3526 The Teacher’s Side of Math(AOJ 1284, BOJ 3904, Gym 101415J, UVa 1397)

http://poj.org/problem?id=3526 https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1284 https://codeforces.com/gym/101415/attachments https://www.acmicpc.net/problem/3904 https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=4143

https://vjudge.net/problem/POJ-3526 https://vjudge.net/problem/Aizu-1284 https://vjudge.net/problem/Gym-101415J https://vjudge.net/problem/Baekjoon-3904 https://vjudge.net/problem/UVA-1397

問題概要

  • 整数$a,m,b,n$が与えられます。以下の条件を満たす多項式 $F(x) = a_d x^d + a_{d-1} x^{d-1} + \cdots + a_1 x + a_0$ を求めてください
    • 係数$a_0,\cdots,a_q$は整数で、$a_q>0$
    • $f(\sqrt[m] a+\sqrt[n] b)=0$
    • 上2つの条件を満たす多項式の中で次数が最小
    • $\gcd(a_0, \cdots, a_q)=1$

制約

  • マルチテストケース
  • $a,b$が異なる素数
  • $1<m,n$
  • $\sqrt[m]{a}+\sqrt[n]{b}\leq 4$
  • $mn \leq 20$
  • 答えの係数 $a_0,\cdots,a_d$ は符号付き32bit整数の範囲に収まる

ヒント

  • 問題文に$a,b$が異なる素数かつ$1<m,n$なら答えの次数は$mn$であり、最上位項$a_d=1$であることが書いてある

解法メモ

  • 入力にも出力にも$a$が登場してややこしいので、$F(x) = c_d x^d + c_{d-1} x^{d-1} + \cdots + c_1 x + c_0$とする

  • $\sqrt[m] a+\sqrt[n] b$を代入すると以下のようになる

    • $c_d(\sqrt[m]{a}+\sqrt[n]{b})^d + c_{d-1}(\sqrt[m]{a}+\sqrt[n]{b})^{d-1} + \cdots + c_1(\sqrt[m]{a}+\sqrt[n]{b}) + c_0=0$
  • これを全て展開し、$(\sqrt[m]{a})^i(\sqrt[n]{b})^j$の係数が0になるように連立方程式を立ててやればよい。

    • $c_d=1$であることが問題文からわかるので、$c_{d-1}, \cdots, c_0$の$d=mn$個の変数を用意してやり、各$0\leq i<m, 0\leq j<n$について$(\sqrt[m]{a})^i(\sqrt[n]{b})^j$の係数が0になるよう式を立てると、ちょうど$mn$次正方行列ができる。
  • これをGauss-Jordan法等を用いて解いてやればよい。

実装例

最初整数だけで実装しようと思ったが、面倒だったので実数で計算した。 初回提出はlong doubleで実装したが、doubleでも普通に通る。

usingなど使っているのでPOJではCEになるので注意

#include <bits/stdc++.h>
using ll = long long;
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define all(v) begin(v), end(v)
using namespace std;

template <typename T>
struct Matrix : vector<T> {
    int n, m;
    Matrix(pair<int, int> p) : n(p.first), m(p.second) { this->resize(n * m); }
    Matrix(int n) : n(n), m(n) { this->resize(n * n); }
    Matrix() : n(0), m(0) {}
    T &operator()(int i, int j) { return (*this)[i * m + j]; }
};
template <typename T>
struct vec : vector<T> {
    int n;
    vec(int n) : n(n) { this->resize(n); }
    vec() : n(0) {}
};

template <typename T>
Matrix<T> new_matrix(int n) {
    Matrix<T> res({n, n});
    return res;
}
template <typename T>
Matrix<T> operator*(const Matrix<T> &m1, const Matrix<T> &m2) {
    assert(m1.m == m2.n);
    Matrix<T> res({m1.n, m2.m});
    rep(i, m1.n) rep(j, m2.m) rep(k, m1.m) { res[i * m2.m + j] += m1[i * m1.m + k] * m2[k * m2.m + j]; }
    return res;
}
template <typename T>
vec<T> operator*(const Matrix<T> &m, const vec<T> &v) {
    assert(m.m == v.n);
    vec<T> res(m.n);
    rep(i, m.n) {
        T sum = 0;
        rep(j, m.m) { sum += m[i * m.m + j] * v[j]; }
        res.push_back(sum);
    }
    return res;
}
template <typename T>
Matrix<T> E(size_t n) {
    Matrix<T> res({n, n});
    rep(i, n) res[i * n + i] = 1;
    return res;
}
template <typename T>
Matrix<T> pow(const Matrix<T> &a, long long n) {
    Matrix<T> b = a;
    Matrix<T> res = E(a.size());
    while (n > 0) {
        if (n & 1) res = res * b;
        b = b * b;
        n >>= 1ll;
    }
    return res;
}

template <typename T>
vec<T> gauss_jordan(const Matrix<T> &A, const vec<T> &b) {  // 連立一次方程式Ax=bを解く
    assert(A.n == A.m);
    assert(A.n == b.n);
    int n = A.n;
    const T eps = 1e-8;
    Matrix<T> B({n, n + 1});
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) B[i * (n + 1) + j] = A[i * n + j];
    for (int i = 0; i < n; i++) B[i * (n + 1) + n] = b[i];

    for (int i = 0; i < n; i++) {
        int pivot = i;
        for (int j = i; j < n; j++) {
            if (abs(B[j * (n + 1) + i]) > abs(B[pivot * (n + 1) + i])) pivot = j;
        }
        for (int j = i; j < n + 1; ++j) swap(B[i * (n + 1) + j], B[pivot * (n + 1) + j]);
        if (abs(B[i * (n + 1) + i]) < eps) return vec<T>();
        for (int j = i + 1; j <= n; j++) B[i * (n + 1) + j] /= B[i * (n + 1) + i];
        for (int j = 0; j < n; j++) {
            if (i != j) {
                for (int k = i + 1; k <= n; k++) B[j * (n + 1) + k] -= B[j * (n + 1) + i] * B[i * (n + 1) + k];
                B[j * (n + 1) + i] = 0;
            }
        }
        B[i * (n + 1) + i] = 1;
    }
    vec<T> x(n);
    for (int i = 0; i < n; i++) x[i] = B[i * (n + 1) + n];
    return x;
}

template <typename T>
T binom(int n, int m) {  // パスカルの三角形
    if (n < m || n < 0 || m < 0) return 0;
    if (m == 0 || m == n) return 1;
    static vector<vector<T>> memo;
    static vector<vector<bool>> memoized;
    while ((int)memo.size() < n + 1) memo.push_back({}), memoized.push_back({});
    while ((int)memo[n].size() < m + 1) memo[n].push_back(0), memoized[n].push_back(false);
    if (memoized[n][m]) return memo[n][m];
    memoized[n][m] = true;
    return memo[n][m] = binom<T>(n - 1, m - 1) + binom<T>(n - 1, m);
}

int main() {
    while (true) {
        int a, m, b, n;
        cin >> a >> m >> b >> n;
        if (a == 0 && m == 0 && b == 0 && n == 0) break;
        Matrix<double> M({n * m, n * m});

        auto idx = [&](int i, int j) -> int { return i * n + j; };  // \sqrt[m]{a}^i+\sqrt[n]{b}^j

        rep(i, n * m) {      // x^iの係数を連立方程式の変数とする
            rep(j, i + 1) {  // (\sqrt[m]{a}+\sqrt[n]{b})^iを展開した時のj番目の係数
                double c = binom<double>(i, j) * pow(a, (i - j) / m) * pow(b, j / n);
                int id = idx((i - j) % m, j % n);
                M(id, i) += c;
            }
        }
        vec<double> v(n * m);  // 最上位項は1固定なのでMx=vのvの部分
        rep(j, n * m + 1) {
            double c = binom<double>(n * m, j) * pow(a, (n * m - j) / m) * pow(b, j / n);
            int id = idx((n * m - j) % m, j % n);
            v[id] -= c;
        }

        vec<double> res = gauss_jordan(M, v);
        assert(!res.empty());
        res.push_back(1);
        reverse(all(res));
        rep(i, n * m + 1) {
            cout << ll(roundl(res[i]));
            if (i != n * m) cout << " ";
        }
        cout << endl;
    }
}