codeforce 1300

COFO::1220B Multiplication Table

cofo problem

COFO::1220B Multiplication Table

Link : COFO::1220B

Problem

level : 1300
tag : math, number theory
TIME
- to understand :
- to algorithm : fail
- to code :
- to debug :
- understaing edit : 1

Point

길이 n의 배열 a가 있습니다.
배열 a 를 행으로 갖는 행열과 배열 a를 열로 갖는 행열의 곱을 구한 결과가 있습니다.
이때 배열 a를 구합니다.

Design

gcd까지 구해서, 약수의 조합으로 풀어보려했지만 TLE 가 예상되었습니다.
한 행 혹은 한 열끼리 빼고는 관계지어서 풀수있는 방법이 안보였는데 edit이 아주 간단한 방법을 제시합니다.
세 원소 x, y, z 가 있을때, 다음과 같은 곱의 결과는 주어진 행열에 무조건 포함됩니다.
- xy yz xz
- 이를 이용해서 x, y, z를 빠르게 구할 수 있습니다.
- xy * xz / yz = x^2

Complexity

O(N)

Code

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cmath>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define r_rep(i, a, b) for(int i=(a); i >(b); i--)
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll n;
ll m[1009][1009];
ll ans[1009];
void solve(){
    cin >> n;
    rep(i, 0, n) rep(j, 0, n) cin >> m[i][j];
    ll a0a1 = m[0][1], a0a2 = m[0][2], a1a2 = m[1][2];
    ans[0] = sqrt(a0a1 * a0a2 / a1a2);
    ans[1] = a0a1 / ans[0];
    ans[2] = a0a2 / ans[0];
    rep(i, 3, n) ans[i] = m[i-1][i] / ans[i-1];
    rep(i, 0, n) cout << ans[i] << " ";
    cout <<'\n';
}
int main(){
    solve();
    return 0;
}