题目描述

高精度加法

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

const int base = 1000000000;

vector[HTML_REMOVED] add(vector[HTML_REMOVED] &A, vector[HTML_REMOVED] &B)
{
if (A.size() < B.size()) return add(B, A);

vector<int> C;
int t = 0;
for (int i = 0; i < A.size(); i ++ )
{
    t += A[i];
    if (i < B.size()) t += B[i];
    C.push_back(t % base);
    t /= base;
}

if (t) C.push_back(t);
return C;

}

int main()
{
string a, b;
vector[HTML_REMOVED] A, B;
cin >> a >> b;

for (int i = a.size() - 1, s = 0, j = 0, t = 1; i >= 0; i -- )
{
    s += (a[i] - '0') * t;
    j ++, t *= 10;
    if (j == 9 || i == 0)
    {
        A.push_back(s);
        s = j = 0;
        t = 1;
    }
}
for (int i = b.size() - 1, s = 0, j = 0, t = 1; i >= 0; i -- )
{
    s += (b[i] - '0') * t;
    j ++, t *= 10;
    if (j == 9 || i == 0)
    {
        B.push_back(s);
        s = j = 0;
        t = 1;
    }
}

auto C = add(A, B);

cout << C.back();
for (int i = C.size() - 2; i >= 0; i -- ) printf("%09d", C[i]);
cout << endl;

return 0;

}

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla