백준 3397번 Division Expression

https://www.acmicpc.net/problem/3397

 

괄호가 없는 x1/x2/x3/ ... /xk를 생각해 보자. 분자에는 x1 하나만 있고 다른 수는 전부 분모가 된다.

괄호를 이용한 기본적인 식 (x1/x2) / (x3/x4)를 보면 나눗셈의 앞부분에는 영향이 없지만 나눗셈 뒤에 오는 괄호 안의 분수는 역수로 취해져 분자와 분모가 바뀌게 된다. 괄호가 없을때와 비교하면 x3는 그대로 나누어지지만 x4는 곱해지게 된다.

우선 괄호를 어디에 두더라도 x1은 분자, x2는 분모에 위치한다는 것을 알 수 있다. 정수를 만드려면 분모의 인수가 적을수록 유리함으로 분모에 곱해지는 수는 최소화 해야한다. x1/(x2/x3/x4/.../xk)를 하면 (x1*x3*x4*...*xk) / x2가 되어 유클리드 호재법으로 x2에 다른 수와의 최대공약수를 전부 나누어서 1로 만들수 있다면 결과값이 정수가 된다.

 

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b){
    if (!b) return a;
    return gcd(b, a % b);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int d;
    cin >> d;
    
    while (d--){
        int n;
        cin >> n;
        int x1, x2;
        cin >> x1 >> x2;
        x2 /= gcd(x1, x2);
        for (int i = 2; i < n; i++){
            cin >> x1;
            x2 /= gcd(x1, x2);
        }
        
        if (x2 == 1) cout << "YES\n";
        else cout << "NO\n";
    }
}