正经题解｜ N - 9的倍数

题目分析

$N$ 最大为 $10 ^ {200000}$，显然超出整数正常处理范围，可以使用高精度除法但这题有更便捷的做法。

以下给出本题的部分方法。

方法一：$9$ 的倍数含有性质，如果一个数是 $9$ 的倍数，它们的各位数字之和一定是9的倍数。这是因为一个数被9整除，当且仅当它的各位数字之和被9整除。

方法二：利用同余性质，N % 9 == 0，把 $N$ 拆成各个位数相加，如将 123 拆成 100 + 20 + 3，计算过程同时求余即可。

AC代码

方法一

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int main() {
    string n;
    cin >> n;
    int sum = 0;
    for(char &i:n) {
        int k = i - '0';
        sum += k;
    }
    if (sum % 9 == 0) {
        cout << "Yes" << endl;
    }else {
        cout << "No" << endl;
    }
    return 0;
}

方法二

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int main() {
    ios::sync_with_stdio(false);
    string n;
    cin >> n;
    int sum = 0;
    for(char &i:n) {
        int k = i - '0';
        sum *= 10;
        sum += k;
        sum %= 9;
    }
    if (sum == 0) {
        cout << "Yes" << endl;
    }else {
        cout << "No" << endl;
    }
    return 0;
}

复杂度分析

计算过程需要用到 $N$ 中的各个位数，则复杂度为 $N$ 的长度，即$O(|N|)$。