洛谷 P1147 连续正整数和

// P1147 的第 ① 版：两重循环枚举左右端点，等差数列公式直接求和
//
// 这是大多数人真实的第一反应 —— 题目说「所有的连续正整数段」，那就把所有段都试一遍。
//
// ⚠ 它有两个毛病，而且**两个都不是算法思想上的错**：
//   ① 没有任何剪枝，一共要跑 M(M−1)/2 次。M = 2×10⁶ 时是 2×10¹² 次，没有任何机会。
//   ② 那个求和公式 (l+r)(r−l+1)/2 在 M 大的时候会**溢出 int**：
//      l = 1、r = M 时它是 (1+M)·M/2 ≈ 2×10¹²，而 int 只到 2.1×10⁹。
//      这里写成 (long long) 才对 —— 溢出之后 sum 会绕回来，可能偶然等于 M，
//      于是打印出一段和根本不等于 M 的区间。
//      ★ 门槛在 M ≥ 65536 左右（M²/2 越过 2³¹），**小样例上一辈子看不见**。
//
// ⇒ 这一版留在这儿是当标准答案用的（对拍时 M 只有几百几千，它不会错也不会慢）。

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

int main() {
    int M;
    if (scanf("%d", &M) != 1) return 0;
    for (int l = 1; l <= M; l++) {
        for (int r = l + 1; r <= M; r++) {
            long long sum = (long long)(l + r) * (r - l + 1) / 2;   // ⚠ 这个 (long long) 不能省
            if (sum == M) printf("%d %d\n", l, r);
        }
    }
    return 0;
}

// P1147 的第 ② 版：还是暴力枚举左端点，只加了两句剪枝
//
//   ① 左端点只需要到 M/2（至少两个数，l + (l+1) ≤ M ⇒ l ≤ (M−1)/2）；
//   ② 往右累加的时候，**和一旦不小于 M 就 break** —— 再往右只会更大。
//
// ★★★ 这一版**已经能 AC 了**，而且不是勉强过：满数据 M = 2×10⁶ 时循环体只跑了
//   一千八百多万次（见 p1147Count.cpp 那张表），本机 0.0x 秒。
//
//   为什么加两句 break 就从 2×10¹² 掉到 1.8×10⁷：
//   左端点是 l 的那一段，累加到超过 M 只要大约 min(√(2M), M/l) 步，
//   把 l = 1…M/2 加起来大约是 M·ln M —— **是 O(M log M)，不是 O(M²)。**
//
// ⇒ 这一页最想说的一句话：**「暴力」和「暴力 + 一句 break」不是同一个东西，
//   它们之间差了十万倍。** 别一看见暴力超时就直接跳去想正解，
//   先问问「这个循环能不能提前退出」。

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

int main() {
    int M;
    if (scanf("%d", &M) != 1) return 0;
    for (int l = 1; l <= M / 2; l++) {
        long long sum = 0;
        for (int r = l; ; r++) {
            sum += r;
            if (sum >= M) {                                  // ← ② 越界就停
                if (sum == M && r > l) printf("%d %d\n", l, r);
                break;
            }
        }
    }
    return 0;
}

// P1147 连续正整数和 —— 能 AC 的那一版：滑动窗口（这一章的模板）
//
// 窗口 [l, r] 里装的是连续正整数 l, l+1, …, r，`sum` 是它们的和。
//   sum < M  ⇒ 右边界往右走一格（和变大）
//   sum > M  ⇒ 左边界往右走一格（和变小）
//   sum = M  ⇒ 记一笔，然后左边界往右走一格（继续找下一个）
//
// ★ 双指针能用的前提：**元素全是正数**，所以「右移 r 一定变大、右移 l 一定变小」。
//   这一章第 3 步讲的就是这条前提 —— 而连续正整数天然满足它，
//   这也是这道题被排进第 7 章题单的原因。
//
// ⚠ 「每一段至少有两个数」是这道题唯一的隐藏条件：窗口起手就是 [1, 2]，
//   循环条件 `l < r` 保证窗口里永远至少两个数。少了它会多输出一行 `M M`（见 p1147One.cpp）。
//
// ★ sum 用 int 够不够？算一笔：进入循环体时 sum ≤ M，`sum += r` 之后最大 M + r ≤ 2M ≤ 4×10⁶，
//   离 int 的 2.1×10⁹ 差 500 倍 —— **够**。
//   ⚠ 但同一道题的暴力版里那个求和公式 (l+r)(r−l+1)/2 最大到 2×10¹²，**int 就装不下**。
//     ⇒ 「要不要 long long」是按每一处的上界分别算的，不是整道题一刀切。

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

int main() {
    int M;
    if (scanf("%d", &M) != 1) return 0;
    int l = 1, r = 2, sum = 3;                  // 窗口 [1, 2]，和是 3
    while (l < r) {                             // ← 窗口里永远至少两个数
        if (sum == M) {
            printf("%d %d\n", l, r);
            sum -= l; l++;
        } else if (sum < M) {
            r++; sum += r;
        } else {
            sum -= l; l++;
        }
    }
    return 0;
}

// P1147 的第 ③ 版：不枚举端点，枚举**段长**—— O(√M)
//
// 长度为 k、左端点为 l 的那一段，和是 k·l + k(k−1)/2。令它等于 M：
//
//        l = (M − k(k−1)/2) / k          ← 要求整除，而且 l ≥ 1
//
// 于是只要 k 从 2 一直试到 k(k+1)/2 ≤ M（也就是 k ≈ √(2M) ≈ 2000）就够了。
// M = 2×10⁶ 时只有 1999 次循环 —— 比滑动窗口还快三个数量级。
//
// ⚠⚠ **但它有一个和算法完全无关的坑，而且能让 100 分变 0 分：输出顺序。**
//   段越长，左端点越小（l 随 k 单调递减）。所以从小到大枚举 k，
//   打印出来的左端点是**降序**的 —— 而题目要求「按左端点大小升序排列」。
//   ⇒ 必须**倒着枚举 k**（见下面那个 for），或者存下来排序。
//   这一条对拍抓得到（p1147MathOrder.cpp 就是顺着枚举的那版），
//   但你得先想到「输出顺序也要对拍」。

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

int main() {
    int M;
    if (scanf("%d", &M) != 1) return 0;
    int kmax = 1;
    while ((long long)(kmax + 1) * (kmax + 2) / 2 <= M) kmax++;   // 保证 l ≥ 1
    for (int k = kmax; k >= 2; k--) {                             // ★ 倒着枚举 ⇒ 左端点升序
        long long t = (long long)M - (long long)k * (k - 1) / 2;
        if (t <= 0 || t % k != 0) continue;
        long long l = t / k;
        printf("%lld %lld\n", l, l + k - 1);
    }
    return 0;
}

// 演示错误写法：窗口允许只装一个数 —— 漏掉了「每一段至少有两个数」
//
// 和 p1147.cpp 的差别只有两处：窗口起手是 [1, 1] 而不是 [1, 2]，循环条件是 `l <= r`。
//
// ★ 后果非常固定：**永远只多出最后那一行 `M M`**（因为 sum = M 且 l = r 只可能是 l = M）。
//   ⇒ 它是那种「样例一眼看不出、提交必挂」的错：样例 M = 10000 的正确输出有 4 行，
//     它输出 5 行，最后一行是 `10000 10000`。
//   ⇒ 对拍抓它的概率是 **100%** —— 每一个 M 都会多这一行。
//     这和 p1147MathOrder（要 M 有两个以上的解才露头）正好是两个极端。

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

int main() {
    int M;
    if (scanf("%d", &M) != 1) return 0;
    int l = 1, r = 1, sum = 1;                  // ← 起手就装了一个数
    while (l <= r) {                            // ← 允许 l == r
        if (sum == M) {
            printf("%d %d\n", l, r);
            sum -= l; l++;
        } else if (sum < M) {
            r++; sum += r;
        } else {
            sum -= l; l++;
        }
    }
    return 0;
}

// 第三方验算：解的个数，能不跑任何一版算法**直接算出来**
//
// 长度 k、左端点 l 的段和是 k·l + k(k−1)/2 = M，两边乘 2：
//
//        2M = k · (2l + k − 1)
//
// 右边两个因子里，k 和 (2l + k − 1) **一奇一偶**（差是 2l−1，奇数）。
// ⇒ 2M 的每一个**奇因子 d** 恰好对应一个解（k 和 2M/d 里谁是奇数就让谁当 d），
//   再去掉 k = 1 那个（只有一个数，不算）。
//
//        解的个数 = (2M 的奇因子个数) − 1
//
// ★★ 两个推论，正文里各占一段：
//   ① **M 是 2 的幂时无解** —— 2M = 2^(a+1) 只有一个奇因子 1，减 1 得 0。
//      而题面写着「保证至少有一个解」⇒ 数据里不会出现 2 的幂。
//   ② 解特别多的 M 是「奇因子特别多」的那些（比如 945 = 3³·5·7）。
//
// 用法：./p1147Odd <N> [csv]   —— 把 M = 10..N 每一个都用滑动窗口数一遍，
//                                 和上面这个公式对，报有几个对不上。

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

/** 滑动窗口数解的个数（和 p1147.cpp 同一份逻辑，只是不打印） */
static int countByWindow(int M) {
    int l = 1, r = 2, sum = 3, c = 0;
    while (l < r) {
        if (sum == M) { c++; sum -= l; l++; }
        else if (sum < M) { r++; sum += r; }
        else { sum -= l; l++; }
    }
    return c;
}

/** 2M 的奇因子个数 */
static int oddDivisors(long long twoM) {
    while (twoM % 2 == 0) twoM /= 2;              // 只剩奇数部分
    int c = 0;
    for (long long d = 1; d * d <= twoM; d++) {
        if (twoM % d) continue;
        c++;                                       // d
        if (d != twoM / d) c++;                    // twoM / d
    }
    return c;
}

int main(int argc, char** argv) {
    int N = (argc > 1) ? atoi(argv[1]) : 20000;
    bool csv = (argc > 2 && string(argv[2]) == "csv");

    int bad = 0, zeroSol = 0, powTwo = 0, powTwoZero = 0, maxSol = 0, argMax = 0;
    for (int M = 10; M <= N; M++) {
        int a = countByWindow(M), b = oddDivisors(2LL * M) - 1;
        if (a != b) bad++;
        if (a == 0) zeroSol++;
        if ((M & (M - 1)) == 0) { powTwo++; if (a == 0) powTwoZero++; }
        if (a > maxSol) { maxSol = a; argMax = M; }
    }
    if (csv) {
        printf("N,%d\nbad,%d\nzeroSol,%d\npowTwo,%d\npowTwoZero,%d\nmaxSol,%d\nargMax,%d\n",
               N, bad, zeroSol, powTwo, powTwoZero, maxSol, argMax);
    } else {
        printf("M = 10 .. %d\n", N);
        printf("窗口数出来的解数 ≠ (2M 的奇因子个数 − 1) 的 M：%d 个\n", bad);
        printf("一个解都没有的 M：%d 个，其中 2 的幂：%d / %d 个\n", zeroSol, powTwoZero, powTwo);
        printf("解最多的 M 是 %d，有 %d 个解\n", argMax, maxSol);
    }
    return 0;
}

// 数据生成器（P1147 对拍用）：`./p1147Gen <seed> [level]`
//
//   level 0（默认）随机 M ∈ [10, 2000]
//   level 1        专挑边界：① 贴着下界的 M = 10..20；
//                            ② **只有一个解**的 M（M = 2^a · p，p 是奇素数 ⇒ 2M 只有两个奇因子）；
//                            ③ **解特别多**的 M（奇因子多的那些，比如 945 = 3³·5·7 的倍数）
//
// ★ 为什么要有 level 1：两个错版露头的条件完全不同 ——
//   p1147One（漏掉「至少两个数」）**每一个 M 都会露**，随便造都抓得到；
//   p1147MathOrder（输出顺序反了）**要 M 至少有两个解**才露得出来，
//   而只有一个解的 M 上它和正解逐字节相同。
//   ⇒ 「专挑只有一个解的 M」这一档，是故意造一批**抓不到**的数据 ——
//     它证明的是「那个 bug 到底靠什么现形」，而不是「能抓多少」。
//
// ⚠ 题面保证「至少有一个解」，所以 2 的幂被排除在外（它们一个解也没有，见 p1147Odd.cpp）。

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

static bool isPow2(int x) { return (x & (x - 1)) == 0; }

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

    int M;
    if (level == 0) {
        do { M = ri(10, 2000); } while (isPow2(M));
    } else {
        int pick = ri(0, 2);
        if (pick == 0) {
            do { M = ri(10, 20); } while (isPow2(M));            // 贴着下界
        } else if (pick == 1) {
            static const int primes[] = {3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
            int p = primes[ri(0, 13)];
            int a = ri(0, 5);
            M = p << a;                                          // 2^a · p ⇒ 只有一个解
            if (M < 10) M *= 4;
        } else {
            static const int rich[] = {105, 135, 189, 315, 405, 495, 585, 675, 693, 819, 945, 1155, 1275, 1485, 1575, 1755};
            M = rich[ri(0, 15)] * (1 << ri(0, 1));               // 奇因子多 ⇒ 解多
        }
    }
    printf("%d\n", M);
    return 0;
}

// 换一把尺子：四种写法的**循环体执行次数**（外加一笔溢出账）
//
// 用法：./p1147Count <M>        人话版（带秒表）
//       ./p1147Count <M> csv    只打 `键,值`，给 check:viz 用
//
// ★ 为什么数次数而不是只看秒表：第 ① 版在满数据上要跑 2×10¹² 次，
//   秒表根本量不完（要几十分钟）。而次数是**算得出来**的：M(M−1)/2。
//   ⇒ 第 45 章那条：**量不动的时候就换尺子。**
//
// ⚠ 反过来也成立（第 5 章 P1219 那条）：次数不是万能的 ——
//   所以能跑的那三版这里同时给了秒表，两把尺子都摆出来。
//
// 最后那三行是溢出账：暴力版里的 (l+r)(r−l+1)/2 在 l = 1、r = M 时有多大，int 装不装得下。

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

static double now_ms() {
    timespec t;
    clock_gettime(CLOCK_MONOTONIC, &t);
    return t.tv_sec * 1000.0 + t.tv_nsec / 1e6;
}

int main(int argc, char** argv) {
    int M = (argc > 1) ? atoi(argv[1]) : 2000000;
    bool csv = (argc > 2 && string(argv[2]) == "csv");

    long long brute = (long long)M * (M - 1) / 2;          // 算出来的，没跑

    long long breakIter = 0;
    double t0 = now_ms();
    for (int l = 1; l <= M / 2; l++) {
        long long sum = 0;
        for (int r = l; ; r++) { breakIter++; sum += r; if (sum >= M) break; }
    }
    double tBreak = now_ms() - t0;

    long long winIter = 0;
    t0 = now_ms();
    {
        int l = 1, r = 2, sum = 3;
        while (l < r) {
            winIter++;
            if (sum == M) { sum -= l; l++; }
            else if (sum < M) { r++; sum += r; }
            else { sum -= l; l++; }
        }
    }
    double tWin = now_ms() - t0;

    long long mathIter = 0;
    t0 = now_ms();
    {
        int kmax = 1;
        while ((long long)(kmax + 1) * (kmax + 2) / 2 <= M) kmax++;
        for (int k = kmax; k >= 2; k--) {
            mathIter++;
            long long t = (long long)M - (long long)k * (k - 1) / 2;
            if (t <= 0 || t % k != 0) continue;
        }
    }
    double tMath = now_ms() - t0;

    long long formulaMax = (long long)(1 + M) * M / 2;     // 暴力版那个公式的最大值
    long long intMax = 2147483647LL;
    long long winSumMax = 2LL * M;                         // 窗口版 sum 的上界：M + r <= 2M

    if (csv) {
        printf("M,%d\nbrute,%lld\nbreak,%lld\nwin,%lld\nmath,%lld\n"
               "bruteOverBreak,%lld\nbreakOverWin,%lld\nwinOverMath,%lld\n"
               "formulaMax,%lld\nformulaFitsInt,%d\nwinSumMax,%lld\nwinSumFitsInt,%d\n",
               M, brute, breakIter, winIter, mathIter,
               brute / breakIter, breakIter / winIter, winIter / mathIter,
               formulaMax, formulaMax <= intMax ? 1 : 0,
               winSumMax, winSumMax <= intMax ? 1 : 0);
    } else {
        printf("M = %d\n\n", M);
        printf("(1) 两重循环（算出来的，没跑）  %14lld 次\n", brute);
        printf("(2) 加两句剪枝                  %14lld 次   %8.1f ms\n", breakIter, tBreak);
        printf("(3) 滑动窗口                    %14lld 次   %8.1f ms\n", winIter, tWin);
        printf("(4) 枚举段长                    %14lld 次   %8.1f ms\n", mathIter, tMath);
        printf("\n(1)/(2) = %lld 倍   (2)/(3) = %lld 倍   (3)/(4) = %lld 倍\n",
               brute / breakIter, breakIter / winIter, winIter / mathIter);
        printf("\n溢出账：暴力版的 (l+r)(r-l+1)/2 最大 %lld，int 上限 %lld => %s\n",
               formulaMax, intMax, formulaMax <= intMax ? "装得下" : "装不下");
        printf("        窗口版的 sum 最大     %lld，int 上限 %lld => %s\n",
               winSumMax, intMax, winSumMax <= intMax ? "装得下" : "装不下");
    }
    return 0;
}