与えられた除法式 $X_1/X_2/X_3/\dots/X_k$ に対して、括弧を任意の位置に挿入して演算順序を変更した際、その結果が整数になるかどうかを判定する問題を考えます。入力として複数のテストケースが与えられ、各ケースごとに整数化が可能か（YES）そうでないか（NO）を出力する必要があります。ここで、$k$は最大で10,000、各$X_i$は最大で100,000,000の正整数です。

この問題における重要な観察は、演算順序をどのように操作しても、$X_2$ は必ず分母（除数）に残るという点です。一方で、$X_1$ および $X_3$ から $X_k$ までの項は、括弧の配置によってすべて分子（被除数）側に移動させることが可能です。したがって、式が取り得る最大の値は以下の形式で表されます。

(X_1 * X_3 * ... * X_k) / X_2

この分数が整数であるかを判定するためには、分母 $X_2$ が分子全体の積で割り切れるかどうかを確認すればよいことになります。しかし、分子の積を直接計算すると非常に大きな数になり、オーバーフローを引き起こすリスクがあります。そこで、分母 $X_2$ を順次約分していくアプローチを採用します。

アルゴリズムの構築

アルゴリズムの核心は、分子になり得る各数 $X_i$ ($i \neq 2$) に対して、$X_2$ との最大公約数（GCD）を求め、$X_2$ をその公約数で割っていくことです。もし最終的に $X_2$ が $1$ になれば、完全に約分された（すなわち整数である）と判断できます。

計算効率を高めるため、ここではユークリッドの互除法よりもビット演算を利用したバイナリGCD（Stein's Algorithm）を実装します。このアルゴリズムは減算とシフトのみを使用するため、大きな数に対しても高速に動作し、計算量は $O(\log(\max(a, b)))$ です。

実装コード

以下は、標準入力からデータを読み込み、判定を行うC++による実装例です。変数名や構造を変更し、可読性と効率を意識して記述しています。

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

// 入力値の最大サイズに合わせてlong longを使用
typedef long long ValueType;

// バイナリGCDアルゴリズム（再帰なしの実装）
ValueType calculateBinaryGcd(ValueType a, ValueType b) {
    if (a == 0) return b;
    if (b == 0) return a;
    
    // aとbが両方偶数の場合、共通因数2を取り出してシフト
    int shift = 0;
    while (((a | b) & 1) == 0) {
        a >>= 1;
        b >>= 1;
        shift++;
    }
    
    // aを奇数にする（2で割れる限り割る）
    while ((a & 1) == 0) {
        a >>= 1;
    }
    
    // どちらかが0になるまで繰り返す
    do {
        // bを奇数にする
        while ((b & 1) == 0) {
            b >>= 1;
        }
        
        // 常に a <= b となるように交換
        if (a > b) {
            swap(a, b);
        }
        b = b - a; // ユークリッドの互除法の減算版
    } while (b != 0);
    
    return a << shift;
}

// 式が整数になり得るかを判定する関数
bool canBeInteger(vector<ValueType>& nums) {
    // X2（インデックス1）は必ず分母に固定される
    ValueType denominator = nums[1];
    
    // X1で約分処理
    denominator /= calculateBinaryGcd(denominator, nums[0]);
    
    // X3以降の項を順番に処理
    for (size_t i = 2; i < nums.size(); ++i) {
        if (denominator == 1) return true; // 既に1なら確定
        denominator /= calculateBinaryGcd(denominator, nums[i]);
    }
    
    return denominator == 1;
}

int main() {
    int testCases;
    if (scanf("%d", &testCases) != 1) return 0;
    
    while (testCases--) {
        vector<ValueType> sequence;
        ValueType val;
        
        // 最初の項を読み込み
        scanf("%lld", &val);
        sequence.push_back(val);
        
        // 区切り文字'/'とそれに続く数値を読み込み
        while (true) {
            char sep = getchar(); // '/'を消費
            if (sep != '/') break;
            
            if (scanf("%lld", &val) != 1) break;
            sequence.push_back(val);
        }
        
        // 判定結果の出力
        if (canBeInteger(sequence)) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    return 0;
}

このプログラムでは、calculateBinaryGcd関数が計算の要となります。元の数値の範囲が大きいため、引き算を行う際の安全性を考慮して符号付き整数型を使用していますが、基本的にはビットシフトによる高速化の恩恵を受けられます。入力の解析部分も、可変長配列（vector）を活用することで、柔軟にデータを扱えるように設計しました。