洛谷 P2651 添加括号III

// P2651 ✗ 错法之二：把分子真的乘出来，再判整除
//
// ★ 结论本身是对的（a₁·a₃···aₙ 能否被 a₂ 整除），错的是**照字面去算**。
//   顶格 n = 10⁴、每个 aᵢ 接近 2³¹ ⇒ 乘积约 **9.6 万位**（十进制）
//   ⇒ 别说 long long，高精度都不该写。
//
// ⚠ 而它**不是一交就死**：小数据上乘积装得下，答案完全正确
//   ⇒ 顺手写的对拍是**精确的 0**，只有值域一大才现形（见页面那张表）。
//
// ★ 这一版刻意用 unsigned long long（绕回是有定义的），
//   否则有符号溢出是 UB、量出来的数字不可复现（本书第 41 / 47 条）。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    if (!(cin >> t)) return 0;
    string out;
    while (t--) {
        int n;
        cin >> n;
        vector<unsigned long long> a(n + 1);
        for (int i = 1; i <= n; i++) cin >> a[i];
        unsigned long long prod = a[1];         // ⚠ 就是这里：真乘
        for (int i = 3; i <= n; i++) prod *= a[i];
        out += (a[2] != 0 && prod % a[2] == 0) ? "Yes\n" : "No\n";
    }
    cout << out;
    return 0;
}

// P2651 正解 —— 一句结论 ＋ 逐个用 gcd 约分
//
// ============ ★★★ 结论：a₁ 必在分子，a₂ 必在分母，其余都能挪到分子 ============
//
//   · a₁ 永远在最前面，无论怎么加括号它都在**分子**上；
//   · a₂ 紧跟着第一个除号，它永远在**分母**上（任何括号都救不了它）；
//   · 而 a₃ … aₙ 中的任意一个 aᵢ，都可以靠 (…/aᵢ) 这种括号把它翻到分子上
//     —— 例如 a₁/a₂/(a₃/a₄) 就把 a₄ 翻上去了；全部翻上去写成 a₁/(a₂/a₃/a₄/…/aₙ)。
//
//   ⇒ 能不能是整数 ⟺ **a₁ · a₃ · a₄ ··· aₙ 能被 a₂ 整除**。
//
// ============ ⚠⚠ 但那个乘积**绝不能真乘出来** ============
//
//   顶格 n = 10⁴、每个 aᵢ 接近 2³¹ ⇒ 乘积约有 **10⁴ × 9.6 ≈ 9.6 万位**（十进制）。
//   ⇒ 连高精度都不该写。
//   ★ 办法：**边乘边约** —— 拿分母 a₂ 去和每一个分子逐个求 gcd 并除掉，
//     分母降到 1 就说明整除。分母只会变小，全程不超过 2³¹。
//
// 复杂度：每组 O(n log a)。

#include <bits/stdc++.h>
using namespace std;

static long long gcdll(long long a, long long b) { while (b) { long long t = a % b; a = b; b = t; } return a; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    if (!(cin >> t)) return 0;
    string out;
    while (t--) {
        int n;
        cin >> n;
        vector<long long> a(n + 1);
        for (int i = 1; i <= n; i++) cin >> a[i];

        long long d = a[2];                     // 唯一的分母
        long long g = gcdll(d, a[1]);           // ★ a₁ 也在分子上，别漏了它
        d /= g;
        for (int i = 3; i <= n && d > 1; i++) { // 分母降到 1 就可以停
            long long gg = gcdll(d, a[i]);
            d /= gg;
        }
        out += (d == 1) ? "Yes\n" : "No\n";
    }
    cout << out;
    return 0;
}

// P2651 第 ① 版：把**所有加括号方式**真算一遍（小 n 专用）
//
// ★ 它是参照物，而且是一条**和正解完全无关的路**（[第 14 章 P1332](/sol/p1332/) 那条规矩）：
//   正解靠的是一句结论（「a₁ 必在分子、a₂ 必在分母、其余随意」），
//   而这一版**根本不用那句结论** —— 它把每一种括号方式的值真的算出来，看有没有一个是整数。
//
// ★ 怎么枚举：表达式 a_l / … / a_r 加完括号之后，最外层一定是某一次除法
//   ⇒ 选一个断点 m，左边算出 X、右边算出 Y，结果就是 X / Y。
//   ⇒ set(l, r) = { X / Y ： m ∈ [l, r−1]，X ∈ set(l, m)，Y ∈ set(m+1, r) }。
//   值全部按**既约分数**存（每步 gcd 约分），去重之后规模才压得住。
//
// ⚠ 只能跑小数据（n ≤ 7、aᵢ ≤ 20）—— 分数的个数是卡特兰数量级。

#include <bits/stdc++.h>
using namespace std;

static long long gcdll(long long a, long long b) { while (b) { long long t = a % b; a = b; b = t; } return a; }

struct Frac { long long p, q; };
static bool operator<(const Frac& a, const Frac& b) { return a.p != b.p ? a.p < b.p : a.q < b.q; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    if (!(cin >> t)) return 0;
    string out;
    while (t--) {
        int n;
        cin >> n;
        vector<long long> a(n + 1);
        for (int i = 1; i <= n; i++) cin >> a[i];

        vector<vector<set<Frac>>> f(n + 2, vector<set<Frac>>(n + 2));
        for (int i = 1; i <= n; i++) f[i][i].insert({a[i], 1});
        for (int len = 2; len <= n; len++)
            for (int l = 1; l + len - 1 <= n; l++) {
                int r = l + len - 1;
                for (int m = l; m < r; m++)
                    for (const Frac& x : f[l][m])
                        for (const Frac& y : f[m + 1][r]) {
                            long long p = x.p * y.q, q = x.q * y.p;   // X / Y
                            long long g = gcdll(p, q);
                            f[l][r].insert({p / g, q / g});
                        }
            }
        bool ok = false;
        for (const Frac& v : f[1][n]) if (v.q == 1) { ok = true; break; }
        out += ok ? "Yes\n" : "No\n";
    }
    cout << out;
    return 0;
}

// P2651 的生成器：./p2651Gen 种子 [档位]
//
// ★ 每个版本靠什么现形：
//   · p2651NoA1（约分漏掉 a₁）→ 要 **a₂ 里有一部分因子只有 a₁ 提供得了**。
//     档 1 是照这条线造的（a₂ = p·q，p 只塞进 a₁，q 只塞进后面）。
//   · p2651Mul（真把分子乘出来）→ 要**乘积撑破 64 位** ⇒ 小值域是精确的 0。
//   · p2651Brute（枚举所有括号方式）→ 它是**正确**的参照物，只能跑小 n。
//
// 档位：
//   0  ★ 顺手写的样子：t ∈ [2,4]，n ∈ [2,6]，aᵢ ∈ [1,20]（小到能和暴力对拍）
//   1  ★★ 专造「a₂ 的一半因子只在 a₁ 里」⇒ 逼出「漏掉 a₁」那个错法
//   2  ★★ 值域接近 2³¹、n ∈ [3,8] ⇒ 乘积撑破 64 位 ⇒ 逼出「真乘」那个错法
//   3  ★ 顶格：t = 100、n = 10⁴、aᵢ ∈ [1, 2³¹−1]（量正解的秒表用）
//   4  ⚠⚠ 专为「真乘」那个错法造的：**真答案是 Yes，而乘积会绕回 2⁶⁴**。
//      做法：a₂ 取一个**含奇因子**的数（如 3·5·7），让 a₁ 是它的倍数（⇒ 一定 Yes），
//      其余 aᵢ 取接近 2³¹ 的大数把乘积顶出去。
//      ★ 为什么 a₂ 必须含奇因子：若 a₂ 是 2 的幂，模 2⁶⁴ 绕回**照样保持整除**
//        ⇒ 那样造出来的还是抓不到（[第 38 章那条](/sol/p3374/)：溢出 ≠ 答错）。
//
// ⚠ 题面 2 ≤ n ⇒ 每组至少两个数；aᵢ ≥ 1。
// ⚠ rng() 一律先落到具名变量再传参。

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char** argv) {
    unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1;
    int mode = argc > 2 ? atoi(argv[2]) : 0;
    mt19937_64 rng(seed * 1000003ull + 20260901ull);

    if (mode == 3) {
        int t = 100;
        printf("%d\n", t);
        for (int c = 0; c < t; c++) {
            int n = 10000;
            printf("%d\n", n);
            for (int i = 1; i <= n; i++) {
                long long v = 1 + (long long)(rng() % 2147483647ull);
                printf("%lld%c", v, i == n ? '\n' : ' ');
            }
        }
        return 0;
    }

    int t = 2 + (int)(rng() % 3u);
    printf("%d\n", t);
    static const long long SMALL[8] = {2, 3, 5, 7, 11, 13, 17, 19};
    for (int c = 0; c < t; c++) {
        int n = (mode == 2 || mode == 4) ? 4 + (int)(rng() % 5u) : 2 + (int)(rng() % 5u);
        printf("%d\n", n);
        vector<long long> a(n + 1);
        if (mode == 1) {
            long long p = SMALL[rng() % 8u], q = SMALL[rng() % 8u];
            a[2] = p * q;
            a[1] = p * (1 + (long long)(rng() % 5u));          // p 只在 a₁ 里
            for (int i = 3; i <= n; i++) a[i] = q * (1 + (long long)(rng() % 5u));
        } else if (mode == 4) {
            static const long long ODD[4] = {105, 15, 231, 45};
            a[2] = ODD[rng() % 4u];
            a[1] = a[2] * (1 + (long long)(rng() % 1000u));
            for (int i = 3; i <= n; i++) a[i] = 2000000000LL + (long long)(rng() % 147483647ull);
        } else if (mode == 2) {
            for (int i = 1; i <= n; i++) a[i] = 1 + (long long)(rng() % 2147483647ull);
        } else {
            for (int i = 1; i <= n; i++) a[i] = 1 + (long long)(rng() % 20ull);
        }
        for (int i = 1; i <= n; i++) printf("%lld%c", a[i], i == n ? '\n' : ' ');
    }
    return 0;
}

// P2651 的度量程序：./p2651Count csv        （本页的数字都出自它）
//
//   digits : ★★★ 顶格时「分子乘积」有多少位十进制 —— 这一个数就说明了**为什么不能真乘**
//            （连高精度都不该写）。
//   over   : ★ 各档里乘积撑破 2⁶⁴ 的轮数 —— 「真乘」那个错法的触发条件。
//   yes    : ⚠ 各档里**正解答案是 Yes** 的轮数 ——
//            它解释了档 2 那个反直觉的 0：乘积明明溢出了，可两版一起输出 No
//            （[「一致有两种：都算对了，和都没算」](/sol/p1746/)）。
//   ms     : 顶格 t = 100、n = 10⁴ 上正解的毫秒。
//
// ⚠ 这里**复刻**了 p2651Gen.cpp 的档位逻辑（同一个 mt19937_64、同一个种子公式）。

#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using namespace std::chrono;

static long long gcdll(long long a, long long b) { while (b) { long long t = a % b; a = b; b = t; } return a; }

/** 复刻 p2651Gen.cpp 的一组（只取第一组表达式，够用了） */
static vector<long long> genCase(unsigned seed, int mode) {
    mt19937_64 rng(seed * 1000003ull + 20260901ull);
    static const long long SMALL[8] = {2, 3, 5, 7, 11, 13, 17, 19};
    static const long long ODD[4] = {105, 15, 231, 45};
    (void)(rng() % 3u);                          // t
    int n = (mode == 2 || mode == 4) ? 4 + (int)(rng() % 5u) : 2 + (int)(rng() % 5u);
    vector<long long> a(n + 1);
    if (mode == 1) {
        long long p = SMALL[rng() % 8u], q = SMALL[rng() % 8u];
        a[2] = p * q;
        a[1] = p * (1 + (long long)(rng() % 5u));
        for (int i = 3; i <= n; i++) a[i] = q * (1 + (long long)(rng() % 5u));
    } else if (mode == 4) {
        a[2] = ODD[rng() % 4u];
        a[1] = a[2] * (1 + (long long)(rng() % 1000u));
        for (int i = 3; i <= n; i++) a[i] = 2000000000LL + (long long)(rng() % 147483647ull);
    } else if (mode == 2) {
        for (int i = 1; i <= n; i++) a[i] = 1 + (long long)(rng() % 2147483647ull);
    } else {
        for (int i = 1; i <= n; i++) a[i] = 1 + (long long)(rng() % 20ull);
    }
    return a;
}

static bool solve(const vector<long long>& a) {
    int n = (int)a.size() - 1;
    long long d = a[2];
    d /= gcdll(d, a[1]);
    for (int i = 3; i <= n && d > 1; i++) d /= gcdll(d, a[i]);
    return d == 1;
}

int main(int argc, char** argv) {
    bool csv = (argc > 1 && string(argv[1]) == "csv");

    /* ① 顶格乘积有多少位 */
    double lg = log10(2147483647.0) * 9999;      // a₁ + a₃…aₙ 共 n−1 = 9999 个因子
    long long digits = (long long)lg + 1;

    /* ② 各档：乘积是否超 2⁶⁴、答案是不是 Yes */
    int over[5] = {0}, yes[5] = {0};
    for (int m : {0, 1, 2, 4}) {
        for (int s = 1; s <= 300; s++) {
            vector<long long> a = genCase(s, m);
            int n = (int)a.size() - 1;
            long double prod = (long double)a[1];
            for (int i = 3; i <= n; i++) prod *= (long double)a[i];
            if (prod > 18446744073709551615.0L) over[m]++;
            if (solve(a)) yes[m]++;
        }
    }

    /* ③ 顶格秒表：t = 100、n = 10⁴ */
    mt19937_64 rng(20260901ull);
    vector<vector<long long>> cases;
    for (int c = 0; c < 100; c++) {
        vector<long long> a(10001);
        for (int i = 1; i <= 10000; i++) a[i] = 1 + (long long)(rng() % 2147483647ull);
        cases.push_back(a);
    }
    int cntYes = 0;
    auto t0 = steady_clock::now();
    for (const auto& a : cases) if (solve(a)) cntYes++;
    double ms = duration<double, milli>(steady_clock::now() - t0).count();

    if (csv) {
        printf("digits,%lld\n", digits);
        for (int m : {0, 1, 2, 4}) printf("over%d,%d\nyes%d,%d\n", m, over[m], m, yes[m]);
        printf("msTop,%.0f\ntopYes,%d\n", ms, cntYes);
        return 0;
    }
    printf("① 顶格 n = 10⁴、每个 aᵢ 接近 2³¹ ⇒ 分子乘积约 **%lld 位**（十进制）\n", digits);
    printf("   ⇒ 别说 long long，连高精度都不该写。\n\n");
    printf("② 各档 300 轮：\n");
    const char* NM[5] = {"0 顺手（值域 20）", "1 a₂ 的因子藏在 a₁ 里", "2 值域接近 2³¹", "", "4 ★ 真答案 Yes ＋ 乘积绕回"};
    for (int m : {0, 1, 2, 4})
        printf("   %-28s 乘积超 2⁶⁴ 的 %3d 轮 ｜ 正解答 Yes 的 %3d 轮\n", NM[m], over[m], yes[m]);
    printf("\n   ⚠ 看第 ③ 行：乘积**次次都溢出**，可正解答 Yes 的只有 %d 轮\n", yes[2]);
    printf("   ⇒ 两版一起输出 No ⇒ 那一档「真乘」那个错法是精确的 0，而它验的是零。\n");
    printf("\n③ 顶格 t = 100、n = 10⁴：正解 %.0f 毫秒（%d 组答 Yes）\n", ms, cntYes);
    return 0;
}