【蓝桥杯】ADV-159 高精度乘法

正文索引 [隐藏]

题目描述:

在C/C++语言中,整型所能表示的范围一般为-2^31到2^31(大约21亿),即使long  long型,一般也只能表示到-2^63到2^63。要想计算更加规模的数,就要用软件来扩展了,比如用数组或字符串来模拟更多规模的数及共运算。现在输入两个整数,请输出它们的乘积。

输入描述:

两行,每行一个正整数,每个整数不超过10000位。

输出描述:

一行,两个整数的乘积。

输入样例:

99
101

输出样例:

9999

解题思路:

将字符串sa、sb分别逆序存入数组a、b中,然后开始相乘进位,最后忽略前置0进行输出即可。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define Up(i,a,b) for(int i = a; i <= b; i++)
#define ms(a,x) memset(a,x,sizeof(a))
const int maxn = 100001;
int a[maxn],b[maxn],c[maxn];   //c存放结果

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    ms(a,0);
    ms(b,0);
    ms(c,0);
    string sa,sb;     
    cin >> sa >> sb;
    int lensa = sa.length()-1;
    int lensb = sb.length()-1;
    Up(i,0,lensa)     //逆序存入a
    {
        a[lensa-i] = sa[i]-'0';
    }
    Up(i,0,lensb)    //逆序存入b
    {
        b[lensb-i] = sb[i]-'0';
    }
    Up(i,0,lensa)   //相乘
    {
        Up(j,0,lensb)   
        {
            c[i+j] += a[i]*b[j];
        }
    }
    Up(i,0,maxn-1)    //进位
    {
        if(c[i] >= 10)
        {
            c[i+1] += c[i]/10;
            c[i] %= 10;
        }
    }
    //输出结果
    int i = maxn-1;
    while(i>0 && c[i]==0)   //忽略前置0
    {
        i--;
    }
    for( ; i >= 0; i--)
    {
        cout << c[i];
    }
    cout << endl;
    return 0;
}