P1303 A*B Problem · 习题解析｜信息学奥赛算法练功房

0题目原文（本地存了一份）

为什么要在这儿抄一份题面

原题在洛谷上（页头有链接）。别人的网站不归我们管，打不开、改版、题号调整都可能发生。所以每个解析页都把题面转录一份存在本地，跟着仓库一起进版本库。

转录自洛谷 P1303，日期见页头。两边不一致时信原站。

题目背景

高精度乘法模板题。

题目描述

给出两个非负整数，求它们的乘积。

输入格式

输入共两行，每行一个非负整数。

输出格式

输出一个非负整数表示乘积。

数据范围

每个非负整数不超过 10²⁰⁰⁰。

时限 1 秒，内存 125 MB（128000 KB）。

输入输出样例

输入

1 
2

输出

官方只给了这一组：1 × 2 = 2。⚠ 第 4 步会看到，它挡住了两个错法、放过了另外两个。

1⚠ 先看一眼这道题和前两道最大的不同：它一档都没有

⚠ 「每个非负整数不超过 10²⁰⁰⁰」—— 就这一句，没有 20%、没有 40%

P1601 的题面写了 20% ＋ 40% 两档，P2142 写了 20% 一档 ⇒ 在那两道题上，「先交一发 64 位整数的」是明码标价的 40 分和 20 分。

这道题一档都没写。

⇒ ★★ 出题人没有递过来的暴力档，就是真的没有。 「先交一发看看」在这道题上是一个纯粹的赌 —— 而两个数各 2001 位，乘积最多 4002 位，unsigned long long 只装得下 19~20 位。

⚠ 顺带一条老熟人：unsigned 的溢出是「模 2⁶⁴ 绕回」，有定义 —— 所以它绕回之后仍然可能碰巧对（只要真实乘积 < 2⁶⁴）。第 43 章 P2822 那条换了道题又出现一次。

p1303Ll.cpp✗ 第 ① 版：64 位整数直接乘 —— 这道题没有给它留分档

// ✗ 第 ① 版：64 位整数直接相乘
//
// ⚠ 这道题和前两道有一处**明显的不同**：[P1601](/sol/p1601/) 的题面写了 20%/40% 两档、
//   [P2142](/sol/p2142/) 写了 20% 一档，而这道题**一档都没有** ——
//   题面只有一句「每个非负整数不超过 10²⁰⁰⁰」。
//
// ⇒ ★★ **出题人没有递过来的暴力档，就是真的没有。**
//   前两道题里「先交一发 64 位的」是明码标价的 20~40 分，这道题它是**一个纯粹的赌**。
//
// ⚠ 用 unsigned long long 是为了让它错得可复现（有符号溢出是 UB）：
//   乘法溢出在 unsigned 下是「模 2⁶⁴ 绕回」，有定义。
//   ⇒ 顺带又一次撞上[第 43 章那条](/sol/p2822/)：**绕回之后它仍然可能碰巧对**
//     —— 只要真实乘积小于 2⁶⁴（约 1.8×10¹⁹，也就是两个数的位数之和不超过 19 位）。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    unsigned long long a = 0, b = 0;
    cin >> a >> b;
    cout << a * b << "\n";
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

2★ 正解：整段代码只有两句话是关键的

★★ `c[i+j] += a[i]*b[j]` ＋结果数组开 `n+m` —— 而两句都靠「倒着存」

c[i + j] += a[i] * b[j];          // ① a 的第 i 位（10ⁱ）乘 b 的第 j 位（10ʲ）落在第 i+j 位
vector<int> c(a.size() + b.size());  // ② 上界是「位数之和」

① 几乎是抄的 —— 前提是下标 0 存个位（第 44 章第 5 步那句「倒着存」）。顺着存的话它得写成 c[(n-1-i)+(m-1-j)] 那种形状，一处写错就全错。 ⚠ 而上一道 P1601 的「左对齐」是同一个病根的另一种发作。

② 这个界是紧的：n 位 × m 位的乘积只可能是 n+m−1 位或者 n+m 位。全枚举 1~3 位的正整数共 998 001 组，0 组例外（其中 82.4% 正好是 n+m 位）。 ⚠ 而这句话有唯一一个例外，就是 0：0 × 1234 只有 1 位，而 n+m−1 = 4 —— 题面写的是「非负整数」，所以这一格得单独想一下。

p1303.cpp★ 正解：先按 i+j 全部累加，最后统一进位

// P1303 A*B Problem —— ★ 正解：竖式乘法，先按 i+j 全部累加，最后统一进位
//
// 整段代码只有两句话是关键的（[第 44 章第 8 步](/ch/44-bignum/)那两句）：
//
//   ① `c[i + j] += a[i] * b[j]`
//      —— a 的第 i 位（10ⁱ）乘 b 的第 j 位（10ʲ）落在第 i+j 位。
//      ★ 这一句几乎是抄的，全靠**倒着存**（下标 0 是个位，下标就是「这一位有多大」）。
//        顺着存的话它得写成 `c[(n-1-i)+(m-1-j)]` 那种形状，一处写错就全错。
//
//   ② 结果数组开 **`a.size() + b.size()`** 位。
//      ★ 上界是「位数之和」，而且这个界是**紧的**：n 位 × m 位的乘积只可能是
//        **n+m−1 位或者 n+m 位**（p1303Count.cpp 把 1~4 位的全枚举了一遍，0 组例外）。
//        少开一位就会在「乘积正好 n+m 位」那些轮次丢掉最高位（p1303Len.cpp 就是它）。
//
// ⚠ 中间的 c[i] 会长到多大？每格最多累加 min(n,m) 个 9×9=81 ——
//   顶格 2001 位时是 **162081**，`int` 上限 2147483647，**余量 13249 倍**。
//   ⇒ 「高精度乘法要开 long long」这条流传很广的话，在这道题上是**不成立的**。
//   ⚠⚠ 但它换个前提就成立：压位到一格 4 位十进制之后，同一个量变成约 **5.0×10¹⁰**，
//     `int` 当场不够（p1303Pack.cpp 那一份就得用 long long）。
//   ⇒ **「要不要 long long」不是数字大小的问题，是你把几位塞进一格的问题。**
//
// 复杂度 O(nm)：顶格 2001 × 2001 ≈ **400 万**次一位数乘法 —— 时限 1 秒，量级差得很远。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string sa, sb;
    if (!(cin >> sa >> sb)) return 0;

    vector<int> a, b;
    for (int i = (int)sa.size() - 1; i >= 0; i--) a.push_back(sa[i] - '0');
    for (int i = (int)sb.size() - 1; i >= 0; i--) b.push_back(sb[i] - '0');

    vector<int> c(a.size() + b.size(), 0);               // ★ 那个「位数之和」
    for (size_t i = 0; i < a.size(); i++)
        for (size_t j = 0; j < b.size(); j++)
            c[i + j] += a[i] * b[j];                     // ★ 那个 i + j

    int carry = 0;
    for (size_t i = 0; i < c.size(); i++) {
        int cur = c[i] + carry;
        c[i] = cur % 10;
        carry = cur / 10;
    }
    while (c.size() > 1 && c.back() == 0) c.pop_back();  // ★ 最高位那一格几乎总是 0

    string s;
    for (int i = (int)c.size() - 1; i >= 0; i--) s += char('0' + c[i]);
    cout << s << "\n";
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★★ 「高精度乘法要开 long long」—— 这条流传很广的话，在这道题上不成立

每个 c[i] 最多累加 min(n, m) 个 9 × 9 = 81。顶格 2001 位 ⇒ 162081。 int 上限 2147483647 ⇒ 余量 13249 倍。⇒ 这道题的正解不需要 long long。

⚠⚠ 但它换个前提就成立：压位到一格四位十进制之后，同一个量变成 501 × 9999² ≈ 5.0×10¹⁰ ⇒ int 当场不够。

⇒ ★★★ 「要不要 long long」不是数字大小的问题，是「你把几位塞进一格、又拿它做什么运算」的问题。 （上一道 P1601 的压位参照物上说过一次同样的话，⚠ 而那次加法压到 9 位 int 都还恰好够得着（19 亿）；换成乘法，压到 4 位就已经从 16 万跳到 500 亿。 ⇒ ★ 真正的主语有两个：压几位，和做加法还是做乘法。）

3⚠ 三个错法 —— 而前两个的触发条件正好互补

p1303Len.cpp✗ 错法一：结果数组开成 n+m−1 —— 恒等于「乘积 mod 10^(n+m−1)」

p1303NoTrim.cpp✗ 错法二：数组开对了，却忘了去前导零 —— 12 × 12 打成 0144

p1303Idx.cpp✗ 错法三：写成 c[i+j+1] —— 恒等于 10 × 正确答案

★★★ 前两个错法的触发条件互补 —— 任何一轮里，两个版本恰好错一个

两个都能证：

乘积正好 n+m 位    =>  Len 错（丢掉最后那次进位）、NoTrim 对（最高位不是 0）
乘积只有 n+m−1 位  =>  Len 对（mod 是恒等变换）、NoTrim 错（最高位是 0，多打一个零）

而上一节刚证过：乘积的位数只可能是这两种。 ⇒ ★★★ 两列抓获数加起来恒等于轮数 —— 四个档位实测都是 300，一次不差。

⇒ 这是「为一个 bug 精心造的档位，正是另一个 bug 的盲区」最干净的一次： 不是「往往如此」，是这两个 bug 在数学上就分掉了整个输入空间。

4⚠ 官方那唯一一组样例 `1 × 2`：挡住两个、放过两个

⚠ 而四个结果的原因全都能说清

版本	样例输出	结论
★ 正解	2
✗ 64 位整数	2	放过 —— 要乘积 ≥ 2⁶⁴ 才问得出来
✗ 数组开 `n+m−1`	2	放过 —— `1 × 2` 只有 1 位（= `n+m−1`），正落在它的盲区
✗ 忘了去前导零	02	★ 一测就死（同一件事：乘积只有 `n+m−1` 位）
✗ 写成 `c[i+j+1]`	20	★ 一测就死（它恒等于 10 × 答案）

⇒ ★★ 有意思的是中间那两行是同一个原因的两面： 1 × 2 的乘积只有 n+m−1 位 —— 这同时是「数组开 n+m−1」的盲区和「忘了去前导零」的必杀。 ⇒ 「这组样例在结构上问不出这个问题」：1 × 2 太小了，它连「进位到最高位」这件事都发生不了。

5★★ 生成器：那个旋钮是「两个数的首位」，而它两头不对称

p1303Pack.cpp参照物：压位乘法（base = 10⁴，必须 long long）—— 1200 轮 0 次不一致

p1303Gen.cpp（四档）生成器：顺手写的 / 首位都 ≤ 3 / 首位都 ≥ 7 / 顶格 2001 位

★★★ 四档 × 四个版本 —— 十六格「触发 ≡ 抓获」一个不差

档位（每档 300 轮）	✗ 64 位	✗ 开 `n+m−1`	✗ 忘了 trim	✗ `c[i+j+1]`	★ 前两列之和
0 ★ 顺手写的（1~12 位，1/8 概率取 `0`）	22	180	120	216	300
1 ⚠ 两数首位都 ≤ 3	28	40	260	300	300
2 ⚠ 两数首位都 ≥ 7	36	300	★ 精确的 0	300	300
3 ★ 顶格（1995~2001 位）	300	254	46	300	300

★★★ 三条读得出来的结论：

★★★ 最后那一列恒等于 300 —— 上一节证过的那件事，四个档位实测一次不差。
★★★ 同一个旋钮的两头不对称，而不对称的原因只有一句话 —— 把两个数的首位都调到 ≥ 7，「忘了去前导零」当场变成能证的精确的 0 （首位之积 ≥ 49 ⇒ 乘积必然是 n+m 位），同时把「开 n+m−1」顶到 300 / 300； ⚠⚠ 可反过来把首位都调到 ≤ 3，只能把「开 n+m−1」压到 40 / 300，压不成 0。 ★ 道理一句话：进位只会往上走，不会往下走 —— 低位攒出来的进位照样能把乘积顶到 n+m 位。 ⇒ ★★ 「把旋钮拧到另一头就能得到另一个精确的 0」是个想当然，两头必须分别量。
★ 「64 位」那一列的触发条件也得写准 —— 一开始写的是「乘积超过 19 位」，实测和抓获数差 2~3 格；改成「两个输入和乘积都要 ≤ 2⁶⁴ − 1」之后才一个不差（20 位的数有一部分仍然小于 2⁶⁴）。 ⇒ 「触发条件也要量，不能推」的又一次，而这次差的只是一个边界。

6★ 哪一版就已经能过了

p1303Count.cpp本页所有数字的出处

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

// P1303 解析页上所有数字的出处。./p1303Count [csv]
//
// 四件事：
//   ① **乘积的位数只可能是 n+m−1 或 n+m** —— 1~4 位的正整数全枚举，0 组例外；
//      ⚠ 而 0 是这句话唯一的例外（`0 × 1234` 只有 1 位）⇒ 题面写「非负」就得单独想一下。
//   ② 四个档位里每个 bug 的触发条件各满足了多少轮 ——
//      ★★★ 其中 Len 和 NoTrim 两列**恒好互补**（相加 ≡ 300），这是能证的。
//   ③ 中间值到底多大：一格一位 vs 压位到一格四位（「要不要 long long」的真正主语）；
//   ④ 顶格要做多少次一位数乘法。
#include <bits/stdc++.h>
using namespace std;

static string mulStr(const string& x, const string& y) {
    vector<int> a, b;
    for (int i = (int)x.size() - 1; i >= 0; i--) a.push_back(x[i] - '0');
    for (int i = (int)y.size() - 1; i >= 0; i--) b.push_back(y[i] - '0');
    vector<int> c(a.size() + b.size(), 0);
    for (size_t i = 0; i < a.size(); i++)
        for (size_t j = 0; j < b.size(); j++) c[i + j] += a[i] * b[j];
    int carry = 0;
    for (size_t i = 0; i < c.size(); i++) { int cur = c[i] + carry; c[i] = cur % 10; carry = cur / 10; }
    while (c.size() > 1 && c.back() == 0) c.pop_back();
    string s;
    for (int i = (int)c.size() - 1; i >= 0; i--) s += char('0' + c[i]);
    return s;
}

/** s（无前导零的十进制串）是不是 <= 2⁶⁴ − 1 = 18446744073709551615 */
static bool fitsU64(const string& s) {
    static const string LIM = "18446744073709551615";
    if (s.size() != LIM.size()) return s.size() < LIM.size();
    return s <= LIM;
}

static void gen(unsigned seed, int mode, string& a, string& b) {
    mt19937 rng(seed * 1000003u + 20260904u);
    int lo = mode == 3 ? 1995 : 1, hi = mode == 3 ? 2001 : 12;
    auto one = [&]() {
        unsigned r = rng() % (unsigned)(hi - lo + 1);
        int len = lo + (int)r;
        string s;
        unsigned h;
        if (mode == 1) { h = rng() % 3u; s += char('1' + h); }
        else if (mode == 2) { h = rng() % 3u; s += char('7' + h); }
        else { h = rng() % 9u; s += char('1' + h); }
        for (int i = 1; i < len; i++) { unsigned d = rng() % 10u; s += char('0' + d); }
        return s;
    };
    a = one(); b = one();
    if (mode == 0) {
        unsigned z1 = rng() % 8u, z2 = rng() % 8u;
        if (z1 == 0) a = "0";
        if (z2 == 0) b = "0";
    }
}

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

    // ① 位数上界：1~3 位的**正**整数全枚举（纯算术，不走高精度那条路）
    auto digits = [](long long v) { int d = 0; while (v > 0) { d++; v /= 10; } return d ? d : 1; };
    int cases = 0, bad = 0, hitFull = 0;
    for (int a = 1; a <= 999; a++)
        for (int b = 1; b <= 999; b++) {
            int n = digits(a) + digits(b), c = digits((long long)a * b);
            cases++;
            if (c != n && c != n - 1) bad++;
            if (c == n) hitFull++;
        }
    // ⚠ 0 是这句话唯一的例外：`0 × 1234` 只有 1 位，而 n+m−1 = 4
    int zeroExc = (int)(mulStr("0", "1234").size() == 1);

    // ② 四个档位的触发计数
    int tLen[4] = {0}, tTrim[4] = {0}, tIdx[4] = {0}, tLl[4] = {0}, sumBoth[4] = {0};
    for (int mode = 0; mode < 4; mode++)
        for (unsigned s = 1; s <= 300; s++) {
            string a, b;
            gen(s, mode, a, b);
            string c = mulStr(a, b);
            size_t n = a.size() + b.size();
            if (c.size() == n) tLen[mode]++;                       // Len 会错
            else tTrim[mode]++;                                    // NoTrim 会错
            sumBoth[mode] = tLen[mode] + tTrim[mode];
            if (c != "0") tIdx[mode]++;                            // Idx（×10）会错
            // ★ 64 位那一版会错的条件写准一点：两个输入**和**乘积都要塞得进 unsigned long long
            //   （「乘积超过 19 位」是个偷懒的近似 —— 20 位的数有一部分仍然 < 2⁶⁴）
            if (!(fitsU64(a) && fitsU64(b) && fitsU64(c))) tLl[mode]++;
        }

    // ③ 中间值
    long long topDigits = 2001;
    long long maxCellBase10 = topDigits * 81;                       // 一格一位
    long long cells4 = (topDigits + 3) / 4;
    long long maxCellBase4 = cells4 * 9999LL * 9999LL;              // 一格四位
    long long intMax = 2147483647LL;
    long long topOps = topDigits * topDigits;

    if (csv) {
        printf("lenCases,%d\n", cases);
        printf("lenBad,%d\n", bad);
        printf("lenFull,%d\n", hitFull);
        printf("zeroExc,%d\n", zeroExc);
        for (int m = 0; m < 4; m++) printf("trigLen%d,%d\n", m, tLen[m]);
        for (int m = 0; m < 4; m++) printf("trigTrim%d,%d\n", m, tTrim[m]);
        for (int m = 0; m < 4; m++) printf("trigIdx%d,%d\n", m, tIdx[m]);
        for (int m = 0; m < 4; m++) printf("trigLl%d,%d\n", m, tLl[m]);
        for (int m = 0; m < 4; m++) printf("sumBoth%d,%d\n", m, sumBoth[m]);
        printf("maxCell10,%lld\n", maxCellBase10);
        printf("maxCell4,%lld\n", maxCellBase4);
        printf("intMax,%lld\n", intMax);
        printf("intMargin10,%.0f\n", (double)intMax / (double)maxCellBase10);
        printf("topOps,%lld\n", topOps);
        return 0;
    }

    printf("=== 乘积的位数只可能是 n+m−1 或 n+m ===\n");
    printf("1~3 位的正整数全枚举，共 %d 组：例外 %d 组；其中正好 n+m 位的 %d 组（%.1f%%）\n",
           cases, bad, hitFull, 100.0 * hitFull / cases);
    printf("⚠ 这句话唯一的例外是 0：`0 × 1234` 只有 1 位（而 n+m−1 = 4）—— 例外确认 %d 处\n\n", zeroExc);

    printf("=== 四个档位 × 每个 bug 的触发条件（各 300 轮）===\n");
    printf("%-40s %6s %6s %6s %6s\n", "触发条件", "档0", "档1", "档2", "档3");
    printf("%-40s %6d %6d %6d %6d\n", "乘积正好 n+m 位（Len 会错）", tLen[0], tLen[1], tLen[2], tLen[3]);
    printf("%-40s %6d %6d %6d %6d\n", "乘积只有 n+m−1 位（NoTrim 会错）", tTrim[0], tTrim[1], tTrim[2], tTrim[3]);
    printf("%-40s %6d %6d %6d %6d\n", "★ 上面两行之和（恒等于轮数）", sumBoth[0], sumBoth[1], sumBoth[2], sumBoth[3]);
    printf("%-40s %6d %6d %6d %6d\n", "乘积不是 0（Idx 会错）", tIdx[0], tIdx[1], tIdx[2], tIdx[3]);
    printf("%-40s %6d %6d %6d %6d\n", "输入或乘积撑破 2⁶⁴（64 位会错）", tLl[0], tLl[1], tLl[2], tLl[3]);

    printf("\n=== 中间值有多大：「要不要 long long」的主语是压位宽度 ===\n");
    printf("一格一位：每格最多 %lld 个 81 相加 ≈ %lld，int 上限 %lld ⇒ 余量 %.0f 倍\n",
           topDigits, maxCellBase10, intMax, (double)intMax / (double)maxCellBase10);
    printf("一格四位：%lld 格 × 9999² ≈ %lld ⇒ **int 不够**，必须 long long\n", cells4, maxCellBase4);
    printf("\n顶格 2001 × 2001 = %lld 次一位数乘法 —— 时限 1 秒\n", topOps);
    return 0;
}

点一下即可编辑

输出

点「运行 ▶」看结果

★ 正解那一版就能过 —— 而 O(nm) 会不会超时是一句乘法

写法	顶格代价	交上去
64 位整数	O(1)	✗ 这道题没给它留分档
★ 竖式 `O(nm)`	2001 × 2001 = 4 004 001 次一位数乘法	★ AC
压位（base 10⁴）	501 × 501 ≈ 25 万次	★ AC，但一分钱不值

⚠ 顶格 400 万次一位数乘法，时限 1 秒 —— 量级差得很远，秒表在这一章量不动 （第 44 章第 4 步）。这一页从头到尾没有一个秒数。 ⇒ 所以这道题不需要分治乘法、更不需要 FFT：O(nm) 在 2001 位上已经绰绰有余。

⇒ 这道题真正要学的三件事：c[i+j] 那一句（靠倒着存白送）、 结果数组开 n+m（一个能证的紧上界）、 乘完要去前导零（因为那个上界几乎总是多留一位）。 ★ 而后两件正好是一对互补的 bug —— 它们分掉了整个输入空间。

洛谷 P1303 A*B Problem

0题目原文（本地存了一份）

输入

输出

1⚠ 先看一眼这道题和前两道最大的不同：它一档都没有

2★ 正解：整段代码只有两句话是关键的

3⚠ 三个错法 —— 而前两个的触发条件正好互补

4⚠ 官方那唯一一组样例 `1 × 2`：挡住两个、放过两个

5★★ 生成器：那个旋钮是「两个数的首位」，而它两头不对称

6★ 哪一版就已经能过了