洛谷 P1372 又是毕业季I

// P1372 正解 —— 答案就是 n / k（整数除法），O(1)
//
// ============ ★ 两半的证明（缺一半就只是「猜对了」）============
//
//   ① **上界**：若能挑出 k 个不同的号数、gcd 为 d，则它们都是 d 的倍数、都 ≤ n
//      ⇒ 至少存在 k 个 ≤ n 的 d 的倍数 ⇒ **k·d ≤ n** ⇒ d ≤ n/k。
//   ② **可达**：取 d = ⌊n/k⌋，那么 d, 2d, …, kd 都 ≤ n，互不相同，
//      而且它们的 gcd 恰好是 d（因为 gcd(d, 2d) 已经是 d 了）。
//
//   ⇒ 答案 = **⌊n / k⌋**，而整数除法自带向下取整。
//
// ★ 题面还给了一句「一个数的最大公约数即本身」⇒ k = 1 时答案是 n ——
//   而 n / 1 = n，公式**自动覆盖**了这个边界，不用特判。
//
// ⚠ 这道题真正考的是「看出它是这件事」，不是 gcd 本身：正解里**一次 gcd 都没调**。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n, k;
    if (!(cin >> n >> k)) return 0;
    cout << n / k << '\n';
    return 0;
}

// P1372 第 ① 版：从大到小试每一个 d
//
// ★ 「k 个人的默契程度 = 他们号数的最大公约数」⇒ 要挑 k 个**互不相同**的号数（1..n），
//   让它们的 gcd 最大。若 gcd 是 d，这 k 个数都是 d 的倍数 ⇒ 至少要有 k 个 ≤ n 的 d 的倍数
//   ⇒ **k·d ≤ n**。
//
// ⇒ 这一版就照这句话枚举：从 n 往下试 d，第一个满足 k·d ≤ n 的就是答案。O(n)。
//
// ⚠⚠ **我的草稿在这儿写的是「顶格 n = 10⁹ 一秒钟悬」—— 实测打回来了：**
//   最坏形状是 k = n（要一路试到 d = 1，整整 10⁹ 次），
//   本机三次实测 **0.24 / 0.24 / 0.25 秒**，而时限是 1 秒 ⇒ **它其实过得去，余量 4 倍**。
//   ★ 道理不玄：这个循环体只有「一次乘法 + 一次比较」，
//     现代 CPU 上 10⁹ 次这种简单循环就是 **0.2 秒量级**（[第 45 章](/ch/45-estimate/)那把尺子）。
//   ⇒ ★★ **「O(n) 配 n = 10⁹ 必然超时」是个想当然 —— 复杂度不等于耗时，循环体里有什么才算。**
//
// ⇒ 所以这一版不是「拿 20 分的暴力」，它是**能 AC 的**；
//   正解 O(1) 赢的不是速度，是「说得清为什么」（见页面第 ② 步那两半证明）。
//
// ⚠ k·d 最大到 10⁹ × 10⁹ = 10¹⁸ ⇒ **必须 long long**（见 p1372Ovf.cpp）。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n, k;
    if (!(cin >> n >> k)) return 0;
    for (long long d = n; d >= 1; d--)
        if (d * k <= n) { cout << d << '\n'; return 0; }
    cout << 0 << '\n';
    return 0;
}

// P1372 的生成器：./p1372Gen 种子 [档位]
//
// ★ 每个版本靠什么现形：
//   · p1372Ovf（判 k·d ≤ n 时用 int）→ 要 **n·k 越过 2³¹**（第一次判断就是 d = n）。
//     ⇒ 顺手写的小数据（n、k 十来个）**结构上抓不到**；档 2 起才有。
//   · p1372Brute → 它是**正确**的（只是慢），抓不到才对。
//
// 档位：
//   0  ★ 顺手写的样子：n ∈ [1, 60]，k ∈ [1, n]
//   1  题面 20% 那一档：n ≤ 10³，k ≤ 2
//   2  ★★ n、k 都大到让 n·k 越过 2³¹（n ∈ [10⁵, 10⁶]，k ∈ [10⁴, n]）
//   3  ★ 顶格：n ∈ [10⁸, 10⁹]，k ∈ [1, n]
//   4  ★ 边界档：k = 1（题面那句「一个数的最大公约数即本身」）或 k = n
//
// ⚠ 题面保证 n ≥ k ≥ 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);

    long long n, k;
    if (mode == 1) { n = 1 + (long long)(rng() % 1000ull); k = 1 + (long long)(rng() % 2ull); if (k > n) k = n; }
    else if (mode == 2) { n = 100000 + (long long)(rng() % 900001ull); k = 10000 + (long long)(rng() % (unsigned long long)(n - 9999)); }
    else if (mode == 3) { n = 100000000LL + (long long)(rng() % 900000001ull); k = 1 + (long long)(rng() % (unsigned long long)n); }
    else if (mode == 4) { n = 1 + (long long)(rng() % 1000000000ull); k = (rng() % 2ull) ? 1 : n; }
    else { n = 1 + (long long)(rng() % 60ull); k = 1 + (long long)(rng() % (unsigned long long)n); }
    printf("%lld %lld\n", n, k);
    return 0;
}

// P1372 的度量程序：./p1372Count csv        （本页的数字都出自它）
//
//   exh  : ★★ 输入空间小的时候「算一遍」比对拍充分 ——
//          把 n ≤ 400、k ≤ n 的**全部** 80 200 组跑一遍，
//          逐组拿 O(n) 暴力核对公式 ⌊n/k⌋，顺带核对「d, 2d, …, kd 真的都 ≤ n 且互不相同」。
//   line : ★ int 溢出那条线是算出来的：n·k > 2³¹ 才会现形 ⇒ 各档里满足它的组数。
//   ms   : 暴力在题面顶格 n = 10⁹ 上要多久（正解是 O(1)）。
//
// ⚠ 这里**复刻**了 p1372Gen.cpp 的档位逻辑（同一个 mt19937_64、同一个种子公式）。

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

static void gen(unsigned seed, int mode, long long& n, long long& k) {
    mt19937_64 rng(seed * 1000003ull + 20260901ull);
    if (mode == 1) { n = 1 + (long long)(rng() % 1000ull); k = 1 + (long long)(rng() % 2ull); if (k > n) k = n; }
    else if (mode == 2) { n = 100000 + (long long)(rng() % 900001ull); k = 10000 + (long long)(rng() % (unsigned long long)(n - 9999)); }
    else if (mode == 3) { n = 100000000LL + (long long)(rng() % 900000001ull); k = 1 + (long long)(rng() % (unsigned long long)n); }
    else if (mode == 4) { n = 1 + (long long)(rng() % 1000000000ull); k = (rng() % 2ull) ? 1 : n; }
    else { n = 1 + (long long)(rng() % 60ull); k = 1 + (long long)(rng() % (unsigned long long)n); }
}

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

    /* ① 全范围穷举 */
    const long long LIM = 400;
    long long total = 0, bad = 0, badWitness = 0;
    for (long long n = 1; n <= LIM; n++)
        for (long long k = 1; k <= n; k++) {
            total++;
            long long f = n / k;
            long long b = 0;
            for (long long d = n; d >= 1; d--) if (d * k <= n) { b = d; break; }
            if (f != b) bad++;
            // ★ 顺带把「可达」那一半也验一遍：d, 2d, …, kd 都 ≤ n
            if (f * k > n) badWitness++;
        }

    /* ② int 溢出那条线：各档里 n·k > 2³¹ 的组数 */
    const long long INT_MAX_LL = 2147483647LL;
    int over[5] = {0};
    for (int m = 0; m < 5; m++)
        for (int s = 1; s <= 300; s++) {
            long long n, k; gen(s, m, n, k);
            if (n * k > INT_MAX_LL) over[m]++;
        }

    /* ③ 换一把机器无关的尺子：暴力要试多少个 d —— 而它有一个闭式 */
    //   从 d = n 往下试到第一个满足 k·d ≤ n 的 d = ⌊n/k⌋ ⇒ 试的次数 = n − ⌊n/k⌋ + 1。
    //   ⇒ k = 1 时一次就中；**k = n 时要试满 n 次**（最坏）。
    long long stepsBad = 0;
    for (long long n = 1; n <= 300; n++)
        for (long long k = 1; k <= n; k++) {
            long long cnt = 0;
            for (long long d = n; d >= 1; d--) { cnt++; if (d * k <= n) break; }
            if (cnt != n - n / k + 1) stepsBad++;
        }
    long long worstSteps = 1000000000LL;          // k = n = 10⁹ ⇒ 试满 10⁹ 次

    /* ④ 真跑一次不可省略的循环，量它一次判断有多贵 */
    volatile long long sink = 0;
    const long long N2 = 200000000LL;
    auto t0 = steady_clock::now();
    for (long long d = N2; d >= 1; d--) { sink += d & 1; }
    double msWorst = duration<double, milli>(steady_clock::now() - t0).count();
    double proj = msWorst * 5.0;                  // 外推到 n = 10⁹
    long long ans = (long long)sink;

    if (csv) {
        printf("exhTotal,%lld\nexhBad,%lld\nexhWitnessBad,%lld\n", total, bad, badWitness);
        for (int m = 0; m < 5; m++) printf("over%d,%d\n", m, over[m]);
        printf("stepsBad,%lld\nworstSteps,%lld\n", stepsBad, worstSteps);
        printf("msWorst,%.0f\nprojMs,%.0f\nans,%lld\n", msWorst, proj, ans);
        return 0;
    }
    printf("① 全范围穷举 n ≤ %lld、k ≤ n（共 %lld 组）：\n", LIM, total);
    printf("   公式 ⌊n/k⌋ 和 O(n) 暴力不一致的组数 = %lld\n", bad);
    printf("   「可达」那一半（d, 2d, …, kd 都 ≤ n）不成立的组数 = %lld\n\n", badWitness);
    printf("② int 溢出那条线（要 n·k > 2³¹）—— 各档 300 轮里满足它的组数：\n");
    const char* NM[5] = {"0 顺手（n ≤ 60）", "1 题面 20% 档（k ≤ 2）", "2 ★ n、k 都大", "3 顶格随机", "4 边界（k = 1 或 k = n）"};
    for (int m = 0; m < 5; m++) printf("   %-26s %3d / 300\n", NM[m], over[m]);
    printf("\n③ 换一把机器无关的尺子：暴力试的次数 = n − ⌊n/k⌋ + 1\n");
    printf("   （n ≤ 300 的全部组合逐组核对这个闭式，不成立的有 %lld 组）\n", stepsBad);
    printf("   ⇒ k = 1 时一次就中；**k = n 时要试满 n 次** ⇒ 顶格 %lld 次\n", worstSteps);
    printf("\n④ 顶格那 10⁹ 次到底有多贵：2×10⁸ 次空转实测 %.0f 毫秒 ⇒ 外推 10⁹ 次约 **%.0f 毫秒**\n",
           msWorst, proj);
    return 0;
}