常考

大数乘法

题目链接：https://leetcode-cn.com/problems/multiply-strings/

class Solution {
public:
    string multiply(string num1, string num2) {
        string res(num1.size() + num2.size(), ‘0‘);

        for(int i = num1.size() - 1; i >= 0; i--)
            for(int j = num2.size() - 1; j >= 0; j--)
            {
                int val = (res[i + j + 1] - ‘0‘) + (num1[i] - ‘0‘) * (num2[j] - ‘0‘);
                res[i + j + 1] = val % 10 + ‘0‘;
                res[i + j]  += val / 10; 
            }
        
        for(int i = 0; i < res.size(); i++)
            if(res[i] != ‘0‘) return res.substr(i);
        
        return "0";
    }
};

大数加法

题目链接：https://leetcode-cn.com/problems/add-strings/

class Solution {
public:
    string addStrings(string num1, string num2) {
        string res;
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        int val = 0;
        for(int i = 0; i < num1.size() || i < num2.size(); i++)
        {
            if(i < num1.size()) val += num1[i] - ‘0‘;
            if(i < num2.size()) val += num2[i] - ‘0‘;
            res.push_back(val % 10 + ‘0‘);
            val /= 10;
        }
        if(val) res.push_back(val + ‘0‘);
        reverse(res.begin(), res.end());
        return res;
    }
};

大数减法

#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool cmp(vector<int> &A, vector<int> &B)
{
    if(A.size() != B.size()) return A.size() > B.size();
    for(int i = A.size() - 1; i >= 0; i--)
        if(A[i] != B[i])
            return A[i] > B[i];
    return true;
}




vector<int> sub_(vector<int> &A, vector<int> &B)
{
    vector<int> C;

    for(int i = 0, t = 0; i < A.size(); ++i)
    {
        t = A[i] - t;
        if(i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if(t < 0) t = 1;
        else t = 0;

    }
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
    
}


int main()
{
    string a, b;
    vector<int> A, B;
    cin>>a>>b;
    
    for(int i = a.size() - 1; i >= 0; --i) A.push_back(a[i] - ‘0‘);
    for(int i = b.size() - 1; i >= 0; --i) B.push_back(b[i] - ‘0‘);
    
    vector<int> C;
    if(cmp(A, B))  C = sub_(A, B);
    else    C = sub_(B, A),  printf("-");;
    for(int i = C.size() - 1; i >= 0; --i) printf("%d", C[i]);
}

大数除法

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

vector<int> div_(vector<int> &A, int b, int &r)
{
    vector<int> C;
    int t = 0;
    for(int i = A.size() - 1; i >= 0; i--)
    {
        t = t * 10 + A[i];
        C.push_back(t / b);
        t %= b;;
    }
    r = t;
    reverse(C.begin(), C.end());
    
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    
    return 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‘);
    int r = 0;
    auto C = div_(A, b, r);
    for(int i = C.size() - 1; i >= 0; --i) cout<<C[i];
    cout<<endl;
    cout<<r<<endl;
    
    
}

n的阶乘（考虑溢出）

#include <iostream>
#include <vector>
#include <string>

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)
    {
        if(i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    return C;
}


int main()
{
    int n;
    cin >> n;
    vector<int> A;
    A.push_back(1);

    for(int i = 1; i <= n; i++)
    {
        A = mul(A, i);
    }
    for(int i = A.size() - 1; i >= 0; i--) cout<<A[i];
    cout<<endl;
}

【算法】【高精度】大数相关问题总结

原文地址：https://www.cnblogs.com/Trevo/p/13321634.html