代码分析

int mystery(int a, int b) {
    if (b == 0) return 0;
    if (b % 2 == 0) return mystery(a + a, b / 2);
    return mystery(a + a, b / 2) + a;
}
cout << mystery(3, 5);

模拟递归调用

mystery(3,5)

• b=5，奇数：return mystery(6, 2) + 3
  • mystery(6,2)，b偶数：return mystery(12,1)
    • mystery(12,1)，b奇数：return mystery(24,0)+12
      • mystery(24,0) → return 0 → 0 +12 =12 → 返回12
• 12 +3 = 15

输出结果：15

\(3 \times5 =15\)，这是俄罗斯农民乘法（倍增乘法）：计算 \(a \times b\)。

原理

思想：把第二个乘数 b 转成二进制。

• b为偶数：\(a\times b = (2a)\times(b/2)\)
• b为奇数：\(a\times b = (2a)\times(b/2)+a\)
• b=0：乘积为0

\[ \begin{align*} 3\times 5 &=3\times(4+1)\ &=3\times4 +3\times1\ &=12+3=15 \end{align*} \]

5的二进制：101，二进制每一位为1就累加此时的a。

完整递归展开栈

mystery(3,5)
    mystery(6,2)
        mystery(12,1)
            mystery(24,0) → 0
        0 + 12 →12
    12
12 +3 →15

小测试

• mystery(2,7) → \(2\times7=14\)
• mystery(4,6) → \(4\times6=24\)

CSP(f(n)=2f(n‑1)+1)J考点

1. 功能：实现 a*b，俄罗斯农民乘法
2. 时间复杂度：\(O(\log b)\)，每次b折半
3. 注意：b不能为负数；b=0直接返回0。

对比汉诺塔：

• hanoi：\(f(n)=2f(n(f(n)=2f(n‑1)+1)1)+1\)
• 本题乘法递归：奇偶分支，倍增a，折半b。

考场快速做题技巧

拿到这种递归看不懂，直接代入小数字模拟，看输入输出猜功能。 试 mystery(2,3)，算出来6，立刻猜是乘法。

思考题

mystery(5,4) 结果等于多少？

快速乘法（俄罗斯农民乘法，倍增乘法） vs 普通循环乘法

代码就是刚才的 mystery(a,b)，本质：二进制拆分乘法，计算 \(a\times b\)

普通循环写法（朴素累加）：

// 循环版：a累加b次，a*b
int mul(int a,int b){
    int res=0;
    for(int i=1;i<=b;i++) res+=a;
    return res;
}

1.时间复杂度对比

• 朴素循环累加：\(\boldsymbol{\(\boldsymbol{\(O(b)\)}\)}\) b如果很大，比如 \(b=10^6\)，循环跑一百万次，很慢。
• 快速倍增乘法：\(\boldsymbol{O(\log b)}\) b每次除以2，循环次数 = b的二进制位数。 \(b=10^6\)，\(\log_2(10^6)\approx20\) 次递归/循环，只跑20次。

核心优点：b越大，优势碾压；b很小看不出差别。

2.算法用途：大整数乘法、模乘法（CSP‑J提高高频）

普通直接写 a*b，在C++里，如果a、b很大，a*b会直接溢出int/long long，得到错误结果。

例：long long a=1e18,b=1e18;，直接 a*b 溢出。 但快速乘可以一边倍增、一边取模，中途不产生超大中间值，防止溢出。

//快速乘取模：计算 (a*b) % mod，避免a*b直接溢出
long long mul_mod(long long a,long long b,long long mod){
    long long res=0;
    while(b>0){
        if(b&1) res=(res+a)%mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return res;
}

• 直接 a*b%mod：中间乘积爆炸溢出，结果错。
• 快速乘：每一步都取模，数值控制在mod以内，不会溢出。

⚠️注意：刚才递归版mystery没有取模，只是演示算法思想；竞赛实际用迭代版快速乘，防止递归栈深度过大。

3.快速乘法缺点

1. b很小的时候（b=2、3）：log₂b也是2次，和普通循环差距不大，没有优势。
2. 递归版快速乘，如果b的二进制位数很大，递归层数太深，会栈溢出；竞赛一般写while循环版本。
3. CPU硬件原生乘法指令非常快！平时做题普通小数字直接写 a*b 最快。 > 快速乘不是用来代替普通 *，而是解决两件事： > ① b极大，不能循环b次；② 大数相乘防止溢出求模。

考场总结（CSP‑J选择题）

快速乘法（倍增乘法）优点

1. 时间复杂度 \(O(\log b)\)，远优于朴素累加循环 \(\(\boldsymbol{\(O(b)\)}\)\)，乘数b越大效率差距越大。
2. 可以改造为快速乘取模算法，解决相乘溢出问题，数论题目必备。
3. 利用二进制拆分思想，和快速幂是一套思想（快速幂：\(a^n\)，也是\(O(\log n)\)）。

记忆：

• 快速乘：\(a\times b\)，拆b二进制，a加倍，b折半
• 快速幂：\(a^b\)，拆b二进制，a平方，b折半 两者逻辑几乎一模一样！

对比记忆

• 朴素循环累加：适合b很小；b大直接超时。
• 快速乘：适合b巨大、大数模运算；小数字没必要。

拓展思考题

快速幂 pow_mod(a,n,mod)，和快速乘结构几乎一样，你能看出哪里改几个变量就从乘法变成幂运算吗？