洛谷 P1888 三角函数

// P1888 ✗ 错法之一：拿「最小的两条边之比」当答案
//
// ⚠⚠ 这一版存在的理由很具体：**本书第 40 章的题单里，那道题的注解原来就是这么写的**
//   （「最小两边之比约分，约的就是 gcd」）—— 而它是错的，2026-09-01 已订正。
//
// ★ 最小两边之比 = 最短边 / 次短边 = **tan(较小锐角)**，不是 sin。
//   sin 要的是「对边 / **斜边**」，而斜边是**最长**的那条。
//
// ★ 官方样例当场就能分辨：`3 5 4` ⇒ 正解 `3/5`，这一版给 `3/4`。
//   ⇒ ⚠ 这是本书里少见的「**样例一测就死**」的错法（连着好几轮拿到的都是反例）。

#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);
    long long v[3];
    if (!(cin >> v[0] >> v[1] >> v[2])) return 0;
    sort(v, v + 3);
    long long lo = v[0], mid = v[1];           // ⚠ 拿的是最小的两条边（那是 tan）
    long long g = gcdll(lo, mid);
    cout << lo / g << '/' << mid / g << '\n';
    return 0;
}

// P1888 正解 —— 最短边 / 斜边，再用 gcd 约分
//
// ★ 这道题只有五行，但它有一处**极容易读错**的地方：
//   「较小锐角的正弦值」——
//     · 直角三角形里，斜边是**最长**的那条（勾股数里最大的那个数）；
//     · 较小的那个锐角，对着**最短**的那条边；
//     · 而 sin(角) = **对边 / 斜边**。
//   ⇒ 答案 = **最短边 / 最长边**。
//
// ⚠⚠ 注意它**不是**「最小的两条边之比」—— 那是 **tan**，不是 sin（见 p1888Tan.cpp）。
//   ★ 官方样例 `3 5 4` 就能分辨：答案是 `3/5`（最短 3、斜边 5），而不是 `3/4`。
//
// ⚠ 输入「无大小顺序」⇒ 不能假定第三个数是斜边，要自己找 min 和 max。
// ⚠ 输出要求约分 ⇒ 除以 gcd。

#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);
    long long a, b, c;
    if (!(cin >> a >> b >> c)) return 0;
    long long lo = min(a, min(b, c));          // 最短边：较小锐角的对边
    long long hi = max(a, max(b, c));          // 最长边：斜边
    long long g = gcdll(lo, hi);
    cout << lo / g << '/' << hi / g << '\n';
    return 0;
}

// P1888 的生成器：./p1888Gen 种子 [档位]
//
// ⚠⚠ **这道题最难写的不是正解，是生成器** —— 题面要的是**勾股数**，
//   而「照题面在 [1, 10⁹] 里随机三个数」造出勾股数的概率约等于 0
//   （p1888Count.cpp 数过：一百万组里 0 组）⇒ 那样测的是一组题目不会给的输入。
//   ⇒ 只能**反着造**：用欧几里得公式 m > n ⇒ (m² − n², 2mn, m² + n²) 一定是勾股数。
//   ★ 这是[第 13 章 P1162](/sol/p1162/) 那条的又一次现场。
//
// ★ 每个版本靠什么现形：
//   · p1888Tan（拿最小两边之比）→ 任何一组勾股数都会错（**连官方样例都挡得住它**）。
//   · p1888NoGcd（忘了约分）→ 要**这组勾股数不是本原的** ⇒ 档 0（本原）是精确的 0，
//     档 1（放大 k 倍）才抓得到。
//
// 档位：
//   0  ★ **本原**勾股数（gcd(m,n) = 1 且一奇一偶）⇒ 忘约分那版是精确的 0
//   1  ★★ 本原勾股数再乘 k（k ∈ [2, 20]）⇒ 忘约分那版必被抓
//   2  两者混着（k ∈ [1, 20]）—— 顺手写的样子
//   3  顶格：m、n 取到让 m² + n² 逼近 10⁹
//
// ⚠ 三个数的**顺序每轮都打乱**（题面明写「无大小顺序」）。
// ⚠ rng() 一律先落到具名变量再传参。

#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(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);

    long long m, n;
    long long hiM = (mode == 3) ? 22000 : 60;         // m² + n² ≤ 10⁹ ⇒ m 最大约 31600
    do {
        m = 2 + (long long)(rng() % (unsigned long long)hiM);
        n = 1 + (long long)(rng() % (unsigned long long)m);
    } while (n >= m || gcdll(m, n) != 1 || ((m - n) % 2 == 0));   // 本原的条件

    long long k = 1;
    if (mode == 1) k = 2 + (long long)(rng() % 19u);
    else if (mode == 2) k = 1 + (long long)(rng() % 20u);
    if (mode == 3) k = 1;

    long long t[3] = { k * (m * m - n * n), k * (2 * m * n), k * (m * m + n * n) };
    for (int i = 2; i > 0; i--) { int j = (int)(rng() % (unsigned long long)(i + 1)); swap(t[i], t[j]); }
    printf("%lld %lld %lld\n", t[0], t[1], t[2]);
    return 0;
}

// P1888 的度量程序：./p1888Count csv        （本页的数字都出自它）
//
//   rand  : ⚠⚠ 「照题面在 [1, 10⁹] 里随机三个数」——**一百万组里有几组真的是勾股数**。
//           这一个数就是「这道题最难写的是生成器」的全部理由。
//   prim  : ★ 各档里**本原**勾股数（gcd(最短边, 斜边) = 1）的组数
//           —— 「忘了约分」那版的触发条件，逐档对上。
//   tan   : ★ 「拿最小两边之比」那版和正解不同的组数 —— 它应该是**满分 300**（连样例都挡得住）。
//   exh   : ★★ 把 m, n ≤ 60 的**全部**本原勾股数枚举一遍，
//           逐组核对「答案 = 最短边/斜边，且已约分」这两件事。
//
// ⚠ 这里**复刻**了 p1888Gen.cpp 的档位逻辑（同一个 mt19937_64、同一个种子公式）。

#include <bits/stdc++.h>
#include <chrono>
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 Tri { long long x, y, z; };

static Tri gen(unsigned seed, int mode) {
    mt19937_64 rng(seed * 1000003ull + 20260901ull);
    long long m, n;
    long long hiM = (mode == 3) ? 22000 : 60;
    do {
        m = 2 + (long long)(rng() % (unsigned long long)hiM);
        n = 1 + (long long)(rng() % (unsigned long long)m);
    } while (n >= m || gcdll(m, n) != 1 || ((m - n) % 2 == 0));
    long long k = 1;
    if (mode == 1) k = 2 + (long long)(rng() % 19u);
    else if (mode == 2) k = 1 + (long long)(rng() % 20u);
    if (mode == 3) k = 1;
    long long t[3] = { k * (m * m - n * n), k * (2 * m * n), k * (m * m + n * n) };
    for (int i = 2; i > 0; i--) { int j = (int)(rng() % (unsigned long long)(i + 1)); swap(t[i], t[j]); }
    return { t[0], t[1], t[2] };
}

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

    /* ① 照题面随机三个数，有几组真的是勾股数 */
    mt19937_64 rng(20260901ull);
    const long long TRIES = 1000000;
    long long hit = 0;
    for (long long i = 0; i < TRIES; i++) {
        long long a = 1 + (long long)(rng() % 1000000000ull);
        long long b = 1 + (long long)(rng() % 1000000000ull);
        long long c = 1 + (long long)(rng() % 1000000000ull);
        long long lo = min(a, min(b, c)), hi = max(a, max(b, c)), mid = a + b + c - lo - hi;
        if (lo * lo + mid * mid == hi * hi) hit++;
    }

    /* ② 各档：本原的组数 + 「拿最小两边」那版的不同组数 */
    int prim[4] = {0}, tanBad[4] = {0};
    for (int m = 0; m < 4; m++)
        for (int s = 1; s <= 300; s++) {
            Tri t = gen(s, m);
            long long lo = min(t.x, min(t.y, t.z)), hi = max(t.x, max(t.y, t.z));
            long long mid = t.x + t.y + t.z - lo - hi;
            if (gcdll(lo, hi) == 1) prim[m]++;
            long long g1 = gcdll(lo, hi), g2 = gcdll(lo, mid);
            if (lo / g1 != lo / g2 || hi / g1 != mid / g2) tanBad[m]++;
        }

    /* ③ 全范围穷举本原勾股数 */
    long long exh = 0, bad = 0;
    for (long long m = 2; m <= 60; m++)
        for (long long n = 1; n < m; n++) {
            if (gcdll(m, n) != 1 || ((m - n) % 2 == 0)) continue;
            long long a = m * m - n * n, b = 2 * m * n, c = m * m + n * n;
            exh++;
            long long lo = min(a, b), g = gcdll(lo, c);
            if (a * a + b * b != c * c) bad++;         // 勾股数本身对不对
            if (g != 1) bad++;                          // 本原 ⇒ 最短边和斜边必互质
        }

    if (csv) {
        printf("randTries,%lld\nrandHit,%lld\n", TRIES, hit);
        for (int m = 0; m < 4; m++) printf("prim%d,%d\ntan%d,%d\n", m, prim[m], m, tanBad[m]);
        printf("exhCount,%lld\nexhBad,%lld\n", exh, bad);
        return 0;
    }
    printf("① 照题面在 [1, 10⁹] 里随机三个数，%lld 组里真的是勾股数的有 **%lld 组**\n", TRIES, hit);
    printf("   ⇒ 「照题面随机」在这道题上造不出一组合法输入，只能用欧几里得公式反着造。\n\n");
    printf("② 各档 300 轮：\n");
    const char* NM[4] = {"0 本原勾股数", "1 放大 k ∈ [2,20] 倍", "2 混着（k ∈ [1,20]）", "3 顶格（本原，逼近 10⁹）"};
    for (int m = 0; m < 4; m++)
        printf("   %-28s 本原的 %3d / 300   ｜ 「最小两边之比」那版不同 %3d / 300\n", NM[m], prim[m], tanBad[m]);
    printf("\n③ 枚举 m, n ≤ 60 的全部本原勾股数：共 %lld 组，其中「不满足勾股定理或最短边与斜边不互质」的有 %lld 组\n",
           exh, bad);
    return 0;
}