算法

(数学) $O(t\log n)$

注意到，一个数如果是 $3$ 的倍数，那么它的 digitsum 一定也是 $3$ 的倍数。所以，至少每三个数里都会存在一个数的 gcdsum 大于 $1$。

C++ 代码

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using ll = long long;

ll gcd_sum(ll n) {
    ll tmp = n, digitsum = 0;

    while (tmp) {
        digitsum += tmp % 10;
        tmp /= 10;
    }

    ll res = std::gcd(n, digitsum);
    return res;
}

int main() {
    int t;
    cin >> t;

    while (t--) {
        ll n;
        cin >> n;
        if (gcd_sum(n) > 1) cout << n << '\n';
        else if (gcd_sum(n + 1) > 1) cout << n + 1 << '\n';
        else if (gcd_sum(n + 2) > 1) cout << n + 2 << '\n';
    }

    return 0;
}