蓝桥杯练习题六 - 大数乘法（c++）

╰+攻爆jí腚メ 2023-09-30 15:12 4阅读 0赞

> 题目如下

对于32位字长的机器，大约超过20亿，用int类型就无法表示了，我们可以选择int64类型，但无论怎样扩展，固定的整数类型总是有表达的极限！如果对超级大整数进行精确运算呢？一个简单的办法是：仅仅使用现有类型，但是把大整数的运算化解为若干小整数的运算，即所谓：“分块法”。

![20160125091111485][]  
上图表示了分块乘法的原理。可以把大数分成多段（此处为2段）小数，然后用小数的多次运算组合表示一个大数。可以根据int的承载能力规定小块的大小，比如要把int分成2段，则小块可取10000为上限值。注意，小块在进行纵向累加后，需要进行进位校正。

请从以下四个选项中选择正确答案，填补在空白处，使得代码能运行后能产生正确的结果。

> 最终代码如下

#include <bits/stdc++.h>
    using namespace std;
    
    void bigmul(int x, int y, int r[])
    {
        int base = 10000;
        int x2 = x / base;
        int x1 = x % base;
        int y2 = y / base;
        int y1 = y % base;
    
        int n1 = x1 * y1;
        int n2 = x1 * y2;
        int n3 = x2 * y1;
        int n4 = x2 * y2;
    
        r[3] = n1 % base;
        r[2] = n1 / base + n2 % base + n3 % base;
        r[1] = n2 / base + n3 / base + n4 % base;
        r[0] = n4 / base;
    
        r[1] += r[2] / base;
        r[2] = r[2] % base;
        r[0] += r[1] / base;
        r[1] = r[1] % base;
    }
    
    int main(int argc, char *argv[])
    {
        int x[] = {0, 0, 0, 0};
    
        bigmul(87654321, 12345678, x);
    
        printf("%d%d%d%d\n", x[0], x[1], x[2], x[3]);
    
        return 0;
    }

这次的练习相对偏中等难度，其实很多时候，都是理念问题，思路对了解起来就容易。下面上解析。

> 解题思路

**1. 获取x1，x2，y1，y2**

int base = 10000;
        int x2 = x / base;
        int x1 = x % base;
        int y2 = y / base;
        int y1 = y % base;

这里有个大前提啊同学们，输入的整数x和y必须是大整数，10000以上的吧，要不然没有意义。

正常我们是十进制，这里按照10000进制，将大整数拆分成两个小一点的整数。

**2.计算x1\*y1，x1\*y1，x2\*y1，x2\*y2的值**

int n1 = x1 * y1;
        int n2 = x1 * y2;
        int n3 = x2 * y1;
        int n4 = x2 * y2;

分别是n1，n2，n3，n4，从上到下。

**3.竖列相加**

r[3] = n1 % base;
        r[2] = n1 / base + n2 % base + n3 % base;
        r[1] = n2 / base + n3 / base + n4 % base;
        r[0] = n4 / base;

题目中是r1～r4，但是我们数组中是从0开始的，所以是r0～r3，大家知道怎么回事就行，别自己搞乱了。备注：特别容易搞乱，注意r1和r\[1\]，带不带方括号很重要，r1=r\[0\].