用户登录
用户注册

分享至

洛谷 P1303 高精度乘高精度

  • 作者: 老衲的鼻毛可是开过光的
  • 来源: 51数据库
  • 2021-07-28

题目链接:点击这里

题意:求两数的积,每个数字不超过 1 0 2000 10^{2000} 102000

思路:假设乘数和被乘数的长度分别为 la 和 lb,那么最后乘积结果的长度最长为 la+lb,最短为 la+lb-1。

AC代码:

#include<iostream>
#include<cstring>

using namespace std;
const int N = 2010;

char A[N], B[N];
int a[N], b[N], c[N];
 
int main()
{
    cin >> A >> B;
    int la = strlen(A), lb = strlen(B);
    
    for(int i = 1; i <= la; i++)    a[i] = A[la - i] - '0';
    for(int i = 1; i <= lb; i++)    b[i] = B[lb - i] - '0';
    
    // a[i] * b[j] 的结果存放在 c[i + j - 1]
    for(int i = 1; i <= la; i++)
    {
        for(int j = 1; j <= lb; j++)
        {
            c[i + j - 1] += a[i] * b[j];
            c[i + j] += c[i + j - 1] / 10;
            c[i + j - 1] %= 10;
        }
    }
    
    int lc = la + lb;
    
    while(c[lc] == 0 && lc > 1) lc--;   // 去掉多余的前导0
    
    for(int i = lc; i >= 1; i--)    cout << c[i];
     
    return 0;
}
软件
前端设计
程序设计
Java相关