题目

题解

题目输入两个数字 $a$, $b$，要求我们求出 $a + b$ 的数位和，首先搞懂什么是数位和，例如数字 $9331$ 的数位和即为 $9 + 3 + 3 + 1 = 16$，简单来说就是每一位的数字的和。

然后我们观察数据范围，发现 $a$, $b$ 的最大值可达 $2^{100}$，我们知道 int 类型的最大值接近 $2^{31}$，long long 类型的最大值接近 $2^{61}$，显然无法存下，所以我们要使用数组去模拟加法。

简单来说，我们用数组表示一个数字，例如数组 $a[0] = 1, a[1] = 8, a[2] = 9$，那么它表示的数字应该是 $981$，严格定义一下就是长度为 $n$ 的数组 $a$ 表示数字 $\sum_{i = 0}^{n – 1} {a[i] \times 10^i}$，如果有两个数组分别为 $a$ $b$，那么模拟它们的和只需要对于每一个数位做个位数加法，再判断和与 $10$ 的关系来决定要不要进位即可。

这个方法的时间复杂度为 $O(N)$（$N$ 代表最大位数），我们知道 $2^{100} < 10^{100}$，因此 $N$ 最大也不会到 $100$，显然可以通过此题。

最后再介绍一下如何读入数字，由于 $a$, $b$ 本身就可能很大，因此我们不可能使用 int 或 long long 存下数字，我们可以使用字符串 string 读入数字，然后对字符 '0' 做减法即可将其还原到数组中。

#include <bits/stdc++.h>

using i128 = __int128;
using ll = long long;
using ull = unsigned long long;
using de = double;
using ld = long double;
using namespace std;

int a[100];
int b[100];
int ans[101];
void solve()
{
    string sa, sb; cin >> sa >> sb;

    int n1 = sa.size(), n2 = sb.size();
    for (int i = 0; i < n1; ++i) a[i] = sa[n1 - 1 - i] - '0';
    for (int i = 0; i < n2; ++i) b[i] = sb[n2 - 1 - i] - '0';
    
    for (int i = 0; i < 100; ++i)
    {
        ans[i] += a[i] + b[i];
        if (ans[i] >= 10) ans[i] %= 10, ans[i + 1]++;
    }

    int sum = 0;
    for (int i = 0; i <= 100; ++i)
    {
        sum += ans[i];
    }

    cout << sum;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    // cin >> t;

    while (t--)
    {
        solve();
    }
}