Gcd Rebuild [CSAcademy #47 C]

https://csacademy.com/contest/round-47/task/gcd-rebuild/

解法

V[y]の値はy行目の要素全てのlcm
U[x]の値はx列目の要素全てのlcm
とする。このとき、10^9を越えるようならダメ。
あとは、構築した後、条件を満たしているかチェックして答えとする。
LCAは普通にやるとバッファオーバーフローするので、閾値を超えたら丸める操作をする必要がある。

typedef long long ll; typedef long double ld;
#define INF 1LL<<60
ld lginf = -1;
ll mul(ll a, ll b) { if (lginf < 0) lginf = log10l(INF); ld aa = log10l(a), bb = log10l(b);
    if (lginf <= aa + bb) return INF; return a * b; }
ll gcd(ll a, ll b) { return a ? gcd(b%a, a) : b; }
ll lcm(ll a, ll b) { if (a == INF || b == INF) return INF; return mul(a / gcd(a, b), b); }


#define MA 1000000000
int N, M;
ll A[303][303];
ll V[303], U[303];
//---------------------------------------------------------------------------------------------------
int solve() {
    rep(y, 0, N) {
        V[y] = 1;
        rep(x, 0, M) V[y] = lcm(V[y], A[y][x]);
        if (MA < V[y]) return 0;
    }

    rep(x, 0, M) {
        U[x] = 1;
        rep(y, 0, N) U[x] = lcm(U[x], A[y][x]);
        if (MA < U[x]) return 0;
    }

    rep(y, 0, N) rep(x, 0, M) {
        if (gcd(V[y], U[x]) != A[y][x]) return 0;
    }

    return 1;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(y, 0, N) rep(x, 0, M) cin >> A[y][x];

    if (solve()) {
        rep(i, 0, N) {
            if (i) printf(" ");
            printf("%lld", V[i]);
        } printf("\n");
        rep(i, 0, M) {
            if (i) printf(" ");
            printf("%lld", U[i]);
        } printf("\n");
    }
    else printf("-1\n");
}