洛谷 P1618 三连击（升级版）

// P1618 的第 ① 版：题目怎么说，代码就怎么写 —— 三个三位数全枚举一遍
//
// 「将 1~9 共 9 个数分成三组，组成三个三位数」⇒ 三个三位数各枚举一遍，
// 每一组都验两件事：九个数字恰好用一次、比例正好是 A:B:C。
//
// ⚠ 比例**不要写成除法**（`x / A == y / B` 整除会截断，一堆假答案）。
//   写成交叉相乘：x : y = A : B  ⇔  x * B == y * A。
//   ★ 顺带把 A = 0 也接住了：B > A = 0，于是 x * B == y * 0 = 0 永不成立，
//     自然输出 No!!! —— 而下一版栽的就是这里。
//
// 它是对的。它也是**跑不完的**：900³ ≈ 7.29 亿组，正文第 ③ 步有秒表。

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

// 九个数字恰好用一次（出现 0 就作废）
bool okDigits(int x, int y, int z) {
    int used = 0;
    for (int v : {x, y, z})
        for (int i = 0; i < 3; i++, v /= 10) {
            int d = v % 10;
            if (d == 0) return false;
            if (used >> d & 1) return false;
            used |= 1 << d;
        }
    return true;
}

int main() {
    int A, B, C;
    cin >> A >> B >> C;
    bool any = false;
    for (int x = 100; x <= 999; x++)
        for (int y = 100; y <= 999; y++)
            for (int z = 100; z <= 999; z++)
                if (okDigits(x, y, z) && x * B == y * A && x * C == z * A) {
                    printf("%d %d %d\n", x, y, z);
                    any = true;
                }
    if (!any) printf("No!!!\n");
    return 0;
}

// P1618 的第 ② 版：只枚举第一个数，另外两个**算**出来
//
// 第 5 章的第一原则：**能算出来的量，不要枚举。**
// 定了 x，比例就把 y、z 钉死了：y = x / A * B、z = x / A * C。
// 900 万分之一的工作量，样例一秒不到就过。
//
// ⚠⚠ 可它是**错的**，而且样例挡不住 —— 两处：
//   ① `x % A != 0` 就跳过 ⇒ 默认「倍数 k = x / A 一定是整数」。
//      可题目给的是**比例**：A:B:C = 2:4:6 和 1:2:3 是同一个比例，
//      而 123 : 246 : 369 正好是 1:2:3 —— 它对 A = 2 不整除，于是被漏掉。
//      （洛谷 2022-08-03 加的两组 Hack 数据打的就是这里。）
//   ② A 可以是 0（题目只保证 0 ≤ A < B < C）⇒ `x % A` 当场除以 0，
//      x86 上直接 SIGFPE，一分不剩。

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

bool okDigits(int x, int y, int z) {
    int used = 0;
    for (int v : {x, y, z})
        for (int i = 0; i < 3; i++, v /= 10) {
            int d = v % 10;
            if (d == 0) return false;
            if (used >> d & 1) return false;
            used |= 1 << d;
        }
    return true;
}

int main() {
    int A, B, C;
    cin >> A >> B >> C;
    bool any = false;
    for (int x = 100; x <= 999; x++) {
        if (x % A != 0) continue;          // ⚠ A = 0 时这一行就是除以 0
        int k = x / A;
        int y = k * B, z = k * C;
        if (y > 999 || z > 999) break;
        if (okDigits(x, y, z)) { printf("%d %d %d\n", x, y, z); any = true; }
    }
    if (!any) printf("No!!!\n");
    return 0;
}

// 把 (A, B, C) 的**整个空间**扫一遍：整除版到底漏了多少组
//
// 用法：./p1618Sweep        人话版
//       ./p1618Sweep csv    只打 `键,值`，给 check:viz 用
//
// ★ 为什么能扫得动：A < B < C ≤ 999 有 C(1000,3) = 166 167 000 组，
//   一组组去解是不可能的。反过来做就很便宜：
//     ① 1~9 的全排列只有 9! = 362 880 种，切成三个三位数就是**全部可能的解**；
//     ② 一组解 (x, y, z) 除掉它们的 gcd，得到**这组解唯一的最简比例** (a, b, c)；
//     ③ 于是「有解的 (A,B,C)」= 某个最简比例的整数倍，t 从 1 数到 999 / c 就完了。
//   ⇒ 有解的组数其实少得可怜，正文那张表里的数就是这么来的。
//
// 整除版（p1618Div.cpp）的判据是 `x % A == 0`，即「倍数 k = x / A 必须是整数」。
// 而 (A,B,C) = t·(a,b,c)、解 (x,y,z) = s·(a,b,c) 时，这个判据等价于 **t | s** ——
// t 不整除 s 的那些解，它一个都看不见。

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

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

    // ① 全排列 -> 所有可能的解，按最简比例分组
    map<array<int, 3>, vector<array<int, 3>>> byRatio;
    int digits[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    long long perms = 0, sols = 0;
    do {
        perms++;
        int x = digits[0] * 100 + digits[1] * 10 + digits[2];
        int y = digits[3] * 100 + digits[4] * 10 + digits[5];
        int z = digits[6] * 100 + digits[7] * 10 + digits[8];
        if (!(x < y && y < z)) continue;         // A < B < C ⇒ 必然 x < y < z
        sols++;
        int g = __gcd(__gcd(x, y), z);
        byRatio[{x / g, y / g, z / g}].push_back({x, y, z});
    } while (next_permutation(digits, digits + 9));

    // ② 每个最简比例的整数倍，就是所有「有解」的 (A, B, C)
    long long solvable = 0, missedTriples = 0, missedLines = 0, missGcd = 0;
    array<int, 3> firstMissed = {0, 0, 0};
    for (auto& [r, list] : byRatio) {
        for (int t = 1; (long long)t * r[2] <= 999; t++) {
            solvable++;
            int A = t * r[0];
            long long miss = 0;
            for (auto& s : list) if (s[0] % A != 0) miss++;
            /* 约分版（p1618Gcd.cpp）：t 被除掉了，判据变成「x 是 a 的倍数」，恒成立 */
            for (auto& s : list) if (s[0] % r[0] != 0) missGcd++;
            if (miss) {
                missedTriples++;
                missedLines += miss;
                if (!firstMissed[2] || array<int, 3>{A, t * r[1], t * r[2]} < firstMissed)
                    firstMissed = {A, t * r[1], t * r[2]};
            }
        }
    }

    long long total = 1000LL * 999 * 998 / 6;    // C(1000,3)：A < B < C ≤ 999
    long long zeroA = 999LL * 998 / 2;           // A = 0 的那些：整除版当场除以 0
    if (csv) {
        printf("perms,%lld\nsolutions,%lld\nratios,%zu\ntotal,%lld\nsolvable,%lld\n"
               "missedTriples,%lld\nmissedLines,%lld\nmissedGcd,%lld\nfirstMissed,%d %d %d\nzeroA,%lld\n",
               perms, sols, byRatio.size(), total, solvable,
               missedTriples, missedLines, missGcd,
               firstMissed[0], firstMissed[1], firstMissed[2], zeroA);
    } else {
        printf("1~9 的全排列                     %lld 种\n", perms);
        printf("其中 x < y < z 的（= 全部可能的解）%lld 组\n", sols);
        printf("它们一共只有                     %zu 个最简比例\n", byRatio.size());
        printf("A < B < C <= 999 一共            %lld 组\n", total);
        printf("  其中有解的只有                 %lld 组\n", solvable);
        printf("  整除版会漏掉解的               %lld 组（共漏 %lld 行答案）\n",
               missedTriples, missedLines);
        printf("  而约分版（p1618Gcd）漏的是     %lld 行\n", missGcd);
        printf("  最小的那一组是                 %d %d %d\n",
               firstMissed[0], firstMissed[1], firstMissed[2]);
        printf("另外 A = 0 的                    %lld 组，整除版直接除以 0\n", zeroA);
    }
    return 0;
}

// P1618 三连击（升级版）—— 能 AC 的那一版
//
// 只枚举第一个数 x（900 个），另外两个用**交叉相乘**反解，一次除法都不做：
//     x : y : z = A : B : C
//   ⇔ y * A == x * B  且  z * A == x * C
//
// 所以 y 必须满足 A | x*B，取 y = x * B / A，再回代验一次（验的是「除得尽」）。
// ★ 这么写，三件事同时被解决：
//   ① 比例不用约分（2:4:6 和 1:2:3 自动等价）；
//   ② 倍数 k 不必是整数（123 : 246 : 369 照样能被找到）；
//   ③ A = 0 也不崩 —— A 是**乘数**不是除数，x*B == y*0 永不成立，自然输出 No!!!。
//
// 枚举 x 是递增的 ⇒ 输出天然「按每行第一个数字升序」，不用再排序。

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

bool okDigits(int x, int y, int z) {
    int used = 0;
    for (int v : {x, y, z})
        for (int i = 0; i < 3; i++, v /= 10) {
            int d = v % 10;
            if (d == 0) return false;       // 含 0 的不行，只能用 1~9
            if (used >> d & 1) return false;  // 重复的不行
            used |= 1 << d;
        }
    return true;
}

int main() {
    int A, B, C;
    cin >> A >> B >> C;
    bool any = false;
    // A = 0 ⇒ 第一个数只能是 0，不可能是三位数。★ 这一行也是「别把 A 当除数」的收益：
    // 它只是一句提前收工，而不是一处「忘了就 RE」的特判。
    for (int x = 123; A > 0 && x <= 987; x++) {
        long long y = 1LL * x * B, z = 1LL * x * C;
        if (y % A || z % A) continue;       // 除不尽 ⇒ 这个 x 配不出整数
        y /= A; z /= A;
        if (y > 999 || z > 999) break;      // z 只会越来越大，可以直接收工
        if (okDigits(x, (int)y, (int)z)) { printf("%d %lld %lld\n", x, y, z); any = true; }
    }
    if (!any) printf("No!!!\n");
    return 0;
}

// 数据生成器（P1618 对拍用）：`./p1618Gen <seed> [level]`
//
//   level 0（默认）顺手写法：随机 1 <= A < B < C <= 999
//   level 1        ★ 反着造：先随机一个 1~9 的排列当**答案**，
//                  切成三个三位数、排好序、除掉 gcd 得到最简比例 (a,b,c)，
//                  再随机乘一个 t，输出 (ta, tb, tc) —— 这样造出来的 (A,B,C) **保证有解**。
//   level 2        ★★ 反着造，而且**逼着 t >= 2**：只留下 c <= 499 的比例（否则 t 只能是 1）。
//
// ★★★ 为什么非要有 level 1（这道题最值钱的一条，正文第 ⑥ 步）：
//   A < B < C <= 999 一共 166 167 000 组，**有解的只有 98 199 组** —— 万分之六。
//   顺手随机 300 轮，几乎每一轮三个版本都齐刷刷输出 No!!!，**对拍全绿而错版还是错的**。
//   要抓漏解，必须**先把「有答案」造出来**。

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

static mt19937 rng;
static int ri(int lo, int hi) { return lo + (int)(rng() % (unsigned)(hi - lo + 1)); }

int main(int argc, char** argv) {
    unsigned seed = (argc > 1) ? (unsigned)atoi(argv[1]) : 1;
    int level = (argc > 2) ? atoi(argv[2]) : 0;
    rng.seed(seed);

    if (level == 0) {
        int a = ri(1, 997), b = ri(a + 1, 998), c = ri(b + 1, 999);
        printf("%d %d %d\n", a, b, c);
        return 0;
    }

    int d[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    shuffle(d, d + 9, rng);
    int v[3] = {d[0] * 100 + d[1] * 10 + d[2],
                d[3] * 100 + d[4] * 10 + d[5],
                d[6] * 100 + d[7] * 10 + d[8]};
    sort(v, v + 3);
    int g = __gcd(__gcd(v[0], v[1]), v[2]);
    int a = v[0] / g, b = v[1] / g, c = v[2] / g;
    if (level >= 2) {
        // ★★ level 1 还不够：整除版只在 t >= 2 时才漏，而最简比例的 c 多半有七八百，
        //    999 / c 就是 1 —— t 被**逼成** 1，于是「保证有解」的数据照样打不假。
        //    这里重摇到 c <= 499 为止，t 才有得选。
        while (c > 499) {
            shuffle(d, d + 9, rng);
            v[0] = d[0] * 100 + d[1] * 10 + d[2];
            v[1] = d[3] * 100 + d[4] * 10 + d[5];
            v[2] = d[6] * 100 + d[7] * 10 + d[8];
            sort(v, v + 3);
            g = __gcd(__gcd(v[0], v[1]), v[2]);
            a = v[0] / g; b = v[1] / g; c = v[2] / g;
        }
    }
    int t = (level >= 2) ? ri(2, 999 / c) : ri(1, 999 / c);   // ⚠ t = 1 时整除版是对的
    printf("%d %d %d\n", a * t, b * t, c * t);
    return 0;
}