题目描述

给定两个非负整数（不含前导 $0$） $A$ 和 $B$，请你计算 $A×B$ 的值。

输入格式

共两行，第一行包含整数 $A$，第二行包含整数 $B$。

输出格式

共一行，包含 $A×B$ 的值。

数据范围

$1≤A的长度≤100000$,
$0≤B≤10000$

输入样例：

2
3

输出样例：

6

算法1

(高精度) $O(n)$

高精度乘法的思想是，拿小的那个数 $b$ 来依次乘上 $A$ 的每一位，有进位的进位。

时间复杂度

参考文献

C++ 代码（无注释版本见高精度乘法）

STL版本（大数×小数）

#include <iostream>
#include <vector>
using namespace std;
vector <int> mul(vector <int> &A,int b){ // 高精度乘法
    vector <int> C; // 答案
    int t = 0; // 每一位相乘的结果
    for(int i = 0;i < A.size() || t;i ++){ // 因为A长度肯定比b大，所以到A的长度就行了，为了节省代码，在后面加上|| t，如果t没有为0，就是还需要进位，就进位
        if(i < A.size()) t += A[i] * b; // 如果还没遍历完A，计算当前位乘b的结果
        C.push_back(t % 10); // C压入t进位后的数
        t /= 10; // 进位
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back(); // 去除前导0
    return C; // 返回答案C
}
int main(){
    string a;
    int b;
    cin>>a>>b;
    vector <int> A;
    for(int i = a.size() - 1;i >= 0;i --) A.push_back(a[i] - '0'); // 倒序A数组
    auto C = mul(A,b); // 计算A × B
    for(int i = C.size() - 1;i >= 0;i --) cout<<C[i];
    cout<<endl;
    return 0;
}

数组版本（大数×小数）

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
string stra;
int lena,lenc;
int a[N],b,c[N];
void mul(int a[],int b){
    int t = 0;
    for(int i = 1;i <= lena || t;i ++){ // 因为是乘法，在计算完a的每一位后，还可能有一次及以上的进位，我们可以将其和到一起写
        if(i <= lena) t += a[i] * b; // 注意要在i还未遍历完a数是相加（不过a数组为全局变量，除数a的几位都为0，去掉if也是没问题的）
        c[++ lenc] = t % 10; // 将答案存入
        t /= 10; // 计算下一次进位
    } 
    while(c[lenc] == 0 && lenc > 1) lenc --; // 去除前导0，讲过多次了，就不讲了
}
int main(){
    cin.tie(0);
    cin>>stra>>b; // 读入
    lena = stra.size();
    for(int i = 1;i <= lena;i ++) a[i] = stra[lena - i] - '0'; // 将数a倒序
    mul(a,b); // 计算
    for(int i = lenc;i >= 1;i --) printf("%d",c[i]); // 反向输出答案
    return 0;
}

数组版本（大数×大数）

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
string stra,strb;
int lena,lenb,lenc;
int a[N],b[N];
long long c[N];
void mul(int a[],int b[]){
    // 大数×大数的基本思想：（模拟一下就很好理解了）
    // 首先把数a和数b每一位相乘，记录在c数组中
    // 然后处理进位
    // 最后将c数组倒序输出
    int t = 0; // 进位
    for(int i = 1;i <= lena;i ++){ // 处理每一位相乘
         for(int j = 1;j <= lenb;j ++){
            c[i + j - 1] += a[i] * b[j];
            lenc = max(lenc,i + j);
         }
    }
    for(int i = 1;i <= lenc || t;i ++){ // 处理进位，这里和大数×小数的思想是一样的
        if(i <= lenc) t += c[i];
        c[i] = t % 10;
        t /= 10;
    }
    while(c[lenc] == 0 && lenc > 1) lenc --; // 去除前导0
}
int main(){ // 与前面相同，因为数b长度扩大，所以也需要放入数组处理
    cin.tie(0);
    cin>>stra>>strb;
    lena = stra.size();
    lenb = strb.size();
    for(int i = 1;i <= lena;i ++) a[i] = stra[lena - i] - '0';
    for(int i = 1;i <= lenb;i ++) b[i] = strb[lenb - i] - '0';
    mul(a,b);
    for(int i = lenc;i >= 1;i --) printf("%d",c[i]);
    return 0;
}

struct 数组模拟（大数×大数）

同样地，我们给出 struct 数组模拟的实用写法。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 1e5 + 10;
struct bignum{
    char s[N];
    int a[N],len;
    bool flag;
    bignum(){
        memset(a,0,sizeof a);
        len = 1;
        flag = 0;
    }
    bignum(int x){
        while(x){
            a[len] = x % 10;
            x /= 10;
            len ++;
        }
        len --;
    }
    int &operator [] (int i){
        return a[i];
    }
    friend bool operator < (bignum a,bignum b){
        if(a.len < b.len) return true;
        if(a.len > b.len) return false;
        for(int i = a.len;i >= 1;i --){
            if(a[i] < b[i]) return true;
            if(a[i] > b[i]) return false;
        }
        return false;
    }
    friend bool operator > (bignum a,bignum b){
        if(a.len < b.len) return false;
        if(a.len > b.len) return true;
        for(int i = a.len;i >= 1;i --){
            if(a[i] < b[i]) return false;
            if(a[i] > b[i]) return true;
        }
        return true;
    }
    friend bool operator == (bignum a,bignum b){
        if(a.len != b.len) return false;
        for(int i = a.len;i >= 1;i --){
            if(a[i] != b[i]) return false;
        }
        return true;
    }
    void input(){
        scanf("%s",s + 1);
        len = strlen(s + 1);
        for(int i = 1;i <= len;i ++) a[i] = s[len - i + 1] - '0';
    }
    void print(){
        if(flag) printf("-");
        for(int i = len;i >= 1;i --) printf("%d",a[i]);
    }
};
bignum operator * (bignum a,bignum b){
    bignum c;
    int t = 0;
    for(int i = 1;i <= a.len;i ++){
         for(int j = 1;j <= b.len;j ++){
            c[i + j - 1] += a[i] * b[j];
            c.len = max(c.len,i + j);
         }
    }
    for(int i = 1;i <= c.len || t;i ++){
        if(i <= c.len) t += c[i];
        c[i] = t % 10;
        t /= 10;
    }
    while(c[c.len] == 0 && c.len > 1) c.len --;
    return c;
}
int main(){
    bignum a,b,c;
    a.input();
    b.input();
    c = a * b;
    c.print();
    return 0;
}

奇奇怪怪的研究

在计算高精度乘法中，大数×小数明显是比大数×大数快的
所以我就想看一下在long long的条件下
c可以容纳下$a[i]×b$
然后在这个值以内的用大数×小数的做法来做，其余用大数×大数来做
然后减少时间复杂度（虽然也没减多少。。。）
所以这个值为$1024819115206086201$

• 计算代码：

#pragma GCC diagnostic error "-std=c++11"
#pragma GCC target("avx")
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks") // 记得加上O3优化，不然跑死人
#include <iostream>
using namespace std;
const long long MAX = 9223372036854775807;
int main(){
    long long i = 1145141919810; // 。可以设更大一点的数
    while(i <= MAX / 9) i ++;
    cout<<i<<endl;
    return 0;
}