P1303 A*B Problem Python题解

A*B Problem

题目背景

高精度乘法模板题。

题目描述

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

1 
2

样例输出 #1

2

提示

每个非负整数不超过 $10^{2000}$。

题解

高精度乘法，洛谷这道题数据不够丰富，至少高精度减法是不能直接int过的，而这道题的所有数据都满足直接用int直接过，那就没什么好说的了。废话，肯定还是得贴一个python的高精度乘法，不然这题解有什么好看的，^ _ ^

先看看高精度乘法字符串实现吧（不然直接int没啥好看的呀）
反转字符串得数字符合低位在数组低位，高位在数组高位，以及恢复大数字等操作可以去看我的高精度减法题解：P2142 高精度减法 Python 题解
这里就不贴这些操作的详细内容了，主要讲讲乘法运算的过程：

1. 乘法竖式运算，一般是小的数放下面，大的数放上面（看人，都行，但是习惯是小在下大在上）
2. 乘法竖式运算最多要有 $len(较小的数)$ 层相加：
   
   这里$len(44)=2$所以有两层数相加
3. 乘法竖式运算最下层数字最多最多有$len(a)+len(b)$位数字，我图方便，直接设成了$2\ast len(较大的数)+1$

下面是代码：

# 反转数字字符串为反转数字列表
def tmpReverse(numStr) -> list:
    tmp = []
    for i in range(len(numStr) - 1, -1, -1):
        tmp.append(ord(numStr[i])-ord("0"))
    return tmp

def reverseBigNum(numStr, lenMAXNum) -> list:
    lenNumStr = len(numStr)
    if lenNumStr == lenMAXNum:
        reverseBN = tmpReverse(numStr)
    else:
        reverseBN = tmpReverse(numStr)
        reverseBN.extend([0 for _ in range(lenMAXNum - lenNumStr)])
    return reverseBN

def recoverBigNum(numList):
    num, tag = "", 0
    for i in range(len(numList)-1, -1, -1):
        if numList[i] != 0:
            tag = i
            break
    for j in range(tag, -1, -1):
        num += str(numList[j])
    return num if num else "0"

# 比较两数的大小
def cmpdayv(numListA, numListB, lenMAXNum):
    for i in range(lenMAXNum-1, -1, -1):
        if numListA[i] == numListB[i]:
            continue
        elif numListA[i] > numListB[i]:
            return 1
        else:
            return -1
    return 0

def add(numListA, numListB):
    lenList = len(numListA)
    ret = [0 for _ in range(lenList)]
    for i in range(lenList):
        ret[i] += numListA[i] + numListB[i]
        if ret[i] >= 10:
            ret[i + 1] += 1
            ret[i] -= 10
    return ret

def mBN1(numListA, numListB, lenMAXNum ,lenMultipleNum):
    mulBN = [[0 for _ in range(lenMultipleNum)] for _ in range(lenMAXNum)]
    for b in range(lenMAXNum):
        for a in range(lenMAXNum):
            mulBN[b][a+b] += numListB[b] * numListA[a]
            if mulBN[b][a+b] >= 10:
                mulBN[b][a+b+1] += mulBN[b][a+b]//10
                mulBN[b][a+b] %= 10
    ret = [0 for _ in range(lenMultipleNum)]
    for i in range(lenMAXNum):
        ret = add(ret, mulBN[i])
    return ret

def multipleBigNum(numListA, numListB, lenMAXNum):
    lenMultipleNum = 2*lenMAXNum + 1
    if cmpdayv(numListA, numListB, lenMAXNum) == 1:
        ret = mBN1(numListA, numListB, lenMAXNum, lenMultipleNum)
    else:
        ret = mBN1(numListB, numListA, lenMAXNum, lenMultipleNum)
    return ret

a = input().strip().replace("\r","")
b = input().strip().replace("\r","")
lenA = len(a)
lenB = len(b)
lenMAXNum = max(lenA, lenB)
numListA = reverseBigNum(a, lenMAXNum)
numListB = reverseBigNum(b, lenMAXNum)
mulBigNum = multipleBigNum(numListA, numListB, lenMAXNum)
print(recoverBigNum(mulBigNum))

在这里再贴一个直接int的代码，python还是轻松滴 ^ _ ^：

a = input().strip()
b = input().strip()
print(int(a)-int(b))