洛谷 P1029 [NOIP 2001 普及组] 最大公约数和最小公倍数问题

// P1029 第 ① 版：老老实实枚举 P 和 Q
//
// ★ 它是参照物。P、Q 都不会超过 y₀（lcm 是两者的倍数）⇒ 双重循环 O(y₀²)。
//   题面 y₀ ≤ 10⁵ ⇒ 最坏 10¹⁰ 次，**过不去**；但小数据上它是最可信的那一份。
//
// ⚠ 这道题**没有分档**（题面只有一句「100% 的数据 2 ≤ x₀, y₀ ≤ 10⁵」）
//   ⇒ 和[第 39 章 P1531](/sol/p1531/) 一样：暴力一分都拿不到。

#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 x0, y0;
    if (!(cin >> x0 >> y0)) return 0;
    long long cnt = 0;
    for (long long p = 1; p <= y0; p++)
        for (long long q = 1; q <= y0; q++) {
            long long g = gcdll(p, q);
            if (g == x0 && p / g * q == y0) cnt++;      // ⚠ 先除后乘：p*q 最大 10¹⁰
        }
    cout << cnt << '\n';
    return 0;
}

// P1029 第 ② 版：把问题缩到「a·b = n 且 gcd(a,b) = 1」，再枚举因子
//
// ============ ★ 关键一步（两行推导）============
//
//   P、Q 的最大公约数是 x₀ ⇒ 记 P = x₀·a、Q = x₀·b，且 **gcd(a, b) = 1**。
//   而 lcm(P, Q) = P·Q / gcd(P, Q) = x₀·a·b = y₀
//   ⇒ **a·b = y₀ / x₀**，记作 n。
//
//   ⇒ 问题变成：**有多少个有序对 (a, b) 满足 a·b = n 且 gcd(a, b) = 1。**
//   ⇒ 枚举 a 到 √n 即可，O(√n)。
//
// ⚠ 而第一件事是判 **y₀ % x₀ != 0 ⇒ 答案是 0**（gcd 一定整除 lcm）——
//   这正是[第 40 章第 7 步](/ch/40-gcd-euclid/)那半章坑的同类（见 p1029NoDiv.cpp）。

#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 x0, y0;
    if (!(cin >> x0 >> y0)) return 0;
    if (y0 % x0 != 0) { cout << 0 << '\n'; return 0; }   // ★ 少了这一句就是一整类错
    long long n = y0 / x0, cnt = 0;
    for (long long a = 1; a * a <= n; a++) {
        if (n % a) continue;
        long long b = n / a;
        if (gcdll(a, b) != 1) continue;
        cnt += (a == b) ? 1 : 2;                          // ⚠ a == b 只能算一次（只有 n = 1 时发生）
    }
    cout << cnt << '\n';
    return 0;
}

// P1029 正解 —— 答案是 2 的「n 有几个不同质因子」次方
//
// ============ ★★★ 接着上一版再推一步 ============
//
//   要 a·b = n 且 gcd(a, b) = 1 ⇒ n 的**每一个质因子的整块幂**，
//   要么整个给 a，要么整个给 b（分开给的话 a、b 就有公因子了）。
//   ⇒ 设 n 有 ω 个不同的质因子，则有序对 (a, b) 恰好有 **2^ω** 个。
//
//   ★ 样例：x₀ = 3、y₀ = 60 ⇒ n = 20 = 2²·5 ⇒ ω = 2 ⇒ 答案 **4**。
//   ★ n = 1（也就是 x₀ = y₀）⇒ ω = 0 ⇒ 答案 **1**（只有 P = Q = x₀ 这一种）。
//
// ⇒ 于是只要**质因数分解 n**，O(√n)，而且连 gcd 都不用调。
// ⚠ 它和第 ② 版是同一个复杂度 —— 写它的理由不是快，是**它把答案的形状说清楚了**
//   （见页面那张「答案只可能是 2 的幂」的表）。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long x0, y0;
    if (!(cin >> x0 >> y0)) return 0;
    if (y0 % x0 != 0) { cout << 0 << '\n'; return 0; }
    long long n = y0 / x0;
    int omega = 0;
    for (long long p = 2; p * p <= n; p++) {
        if (n % p) continue;
        omega++;
        while (n % p == 0) n /= p;
    }
    if (n > 1) omega++;                                   // 剩下的那个大质数
    cout << (1LL << omega) << '\n';
    return 0;
}

// P1029 的度量程序：./p1029Count csv        （本页的数字都出自它）
//
//   legal : ★★★ 照题面随机 (x₀, y₀)，**有多少组是有解的**（y₀ % x₀ == 0）——
//           这一个数解释了「忘了判整除」那版为什么一抓一个准，
//           也解释了**顺手写的「贴心」生成器为什么把它打成精确的 0**。
//   exh   : ★★ 输入空间小的时候，「算一遍」比「对拍」又快又充分 ——
//           把 x₀, y₀ ≤ 120 的 **全部** 组合跑一遍，拿 O(y₀²) 暴力逐组核对 2^ω 那个公式。
//   pow2  : ★ 顺带把答案的**形状**数出来：它只可能是 2 的幂，而且在题面范围里最大是多少。
//   ms    : 顶格上暴力和正解的毫秒。
//
// ⚠ 秒表用 steady_clock 在进程内量。
// ⚠ 这里**复刻**了 p1029Gen.cpp 的档位逻辑（同一个 mt19937、同一个种子公式）。

#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; }

/** 正解：2^ω(y₀/x₀)，无解给 0 */
static long long solve(long long x0, long long y0) {
    if (y0 % x0 != 0) return 0;
    long long n = y0 / x0;
    int w = 0;
    for (long long p = 2; p * p <= n; p++) {
        if (n % p) continue;
        w++;
        while (n % p == 0) n /= p;
    }
    if (n > 1) w++;
    return 1LL << w;
}
/** 暴力：双重枚举 */
static long long brute(long long x0, long long y0) {
    long long c = 0;
    for (long long p = 1; p <= y0; p++)
        for (long long q = 1; q <= y0; q++) {
            long long g = gcdll(p, q);
            if (g == x0 && p / g * q == y0) c++;
        }
    return c;
}

static void genPair(unsigned seed, int mode, long long& x0, long long& y0) {
    mt19937 rng(seed * 1000003u + 20260901u);
    if (mode == 0) { x0 = 2 + (long long)(rng() % 200u); y0 = 2 + (long long)(rng() % 200u); }
    else if (mode == 1) { x0 = 2 + (long long)(rng() % 40u); long long k = 1 + (long long)(rng() % 20u); y0 = x0 * k; }
    else { x0 = 2 + (long long)(rng() % 200u); y0 = x0; }
}

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

    /* ① 三个档位里「有解」的比例 */
    int legal[3] = {0, 0, 0}, nIsOne[3] = {0, 0, 0};
    for (int m = 0; m < 3; m++)
        for (int s = 1; s <= 300; s++) {
            long long x0, y0; genPair(s, m, x0, y0);
            if (y0 % x0 == 0) { legal[m]++; if (y0 / x0 == 1) nIsOne[m]++; }
        }

    /* ② 全范围穷举：x₀, y₀ ≤ LIM 的全部组合 */
    const int LIM = 120;
    long long total = 0, mismatch = 0, nonZero = 0, notPow2 = 0, best = 0;
    for (long long x0 = 2; x0 <= LIM; x0++)
        for (long long y0 = 2; y0 <= LIM; y0++) {
            total++;
            long long a = solve(x0, y0), b = brute(x0, y0);
            if (a != b) mismatch++;
            if (a) { nonZero++; if (a & (a - 1)) notPow2++; if (a > best) best = a; }
        }

    /* ③ 题面范围里答案最大能到多少 */
    long long bigBest = 0, bigX = 0, bigY = 0;
    for (long long x0 = 2; x0 <= 4; x0++)          // ⚠ 题面是 2 ≤ x₀，别从 1 起
        for (long long n = 1; x0 * n <= 100000; n++) {
            long long v = solve(x0, x0 * n);
            if (v > bigBest) { bigBest = v; bigX = x0; bigY = x0 * n; }
        }

    /* ④ 秒表 */
    // ⚠ 正解是亚毫秒级的 —— 单跑一次量到的是噪声（本书第 278 条那一跤）⇒ 跑 REP 次取平均
    long long X = 2, Y = 100000;
    const int REP = 20000;
    long long r1 = 0;
    auto t0 = steady_clock::now();
    // ⚠ 每一次都必须真的走完质因数分解 —— 让 y₀ 恒为 x₀ 的倍数，
    //   否则一半的调用在 `y0 % x0` 那一句就返回了，量到的是空壳（本书踩过好几次的那件事）。
    long long acc = 0;
    for (int i = 0; i < REP; i++) { r1 = solve(X, Y - 2 * (i % 100)); acc += r1; }
    double usFast = duration<double, micro>(steady_clock::now() - t0).count() / REP;
    if (acc == 0) usFast = -1;                     // ★ 自检：真跑过就不可能全是 0
    long long X2 = 2, Y2 = 4000;                  // 暴力只能量到这个规模
    t0 = steady_clock::now(); long long r2 = brute(X2, Y2);
    double msBrute = duration<double, milli>(steady_clock::now() - t0).count();
    double proj = msBrute * ((double)Y * Y) / ((double)Y2 * Y2) / 1000.0;   // 外推到顶格（秒）

    if (csv) {
        for (int m = 0; m < 3; m++) printf("legal%d,%d\nnone%d,%d\n", m, legal[m], m, nIsOne[m]);
        printf("exhTotal,%lld\nexhMismatch,%lld\nexhNonZero,%lld\nexhNotPow2,%lld\nexhBest,%lld\n",
               total, mismatch, nonZero, notPow2, best);
        printf("bigBest,%lld\nbigX,%lld\nbigY,%lld\n", bigBest, bigX, bigY);
        printf("msFastUs,%.2f\nmsBrute,%.0f\nprojSec,%.0f\nans,%lld\nansB,%lld\n",
               usFast, msBrute, proj, r1, r2);
        return 0;
    }

    printf("① 照题面随机 (x₀, y₀) 300 轮，有解（y₀ %% x₀ == 0）的组数：\n");
    const char* NM[3] = {"0 照题面随机", "1 ★ 先挑 x₀ 再挑倍数（顺手的「贴心」写法）", "2 专造 x₀ == y₀"};
    for (int m = 0; m < 3; m++)
        printf("   %-42s %3d / 300   其中 n = 1 的 %3d 组\n", NM[m], legal[m], nIsOne[m]);

    printf("\n② 全范围穷举 x₀, y₀ ∈ [2, %d]（共 %lld 组，逐组拿 O(y₀²) 暴力核对）：\n", LIM, total);
    printf("   正解和暴力不一致的组数 = %lld\n", mismatch);
    printf("   答案非 0 的 %lld 组里，**不是 2 的幂**的有 %lld 组；这一段里最大答案 %lld\n",
           nonZero, notPow2, best);
    printf("\n③ 题面范围（y₀ ≤ 10⁵）里答案最大是 %lld（x₀ = %lld, y₀ = %lld）\n", bigBest, bigX, bigY);
    printf("\n④ 秒表：正解在顶格 (%lld, %lld) 上 **%.1f 微秒**（跑 %d 次取平均 —— 亚毫秒的东西不能只跑一次）；\n",
           X, Y, usFast, REP);
    printf("   暴力在 (%lld, %lld) 上就要 %.0f 毫秒 ⇒ 按 y₀² 外推到顶格约 **%.0f 秒**\n",
           X2, Y2, msBrute, proj);
    return 0;
}