【精進6】ABC387-E

前回のABCのupsolve。答え見ちゃったけど思ったよりギャグ

問題

自然数について、自身の桁和が自身を割り切るとき良い整数と呼ぶ。$N\le a<2N$かつ$a,a+1$がともに良い整数となるような$a$が存在するならば$1$つ求めよ。

解法

$a$が$8$の倍数かつ桁和が$8$で、$a+1$の桁和が$9$であるような$N\le a<2N$は条件を満たす。

これだけ。小さい$N$については愚直に求める。$N$が大きいときは$a$の下$3$桁を$0$にすることで$8$の倍数であるという条件と、$a+1$の桁和が$9$であるという条件が満たされる。あとは上の方の数字を少し増やして桁和が$8$となるよう調整すれば良い。

#include "template.hpp"
ll keta(ll n) {
    ll res = 0;
    while(n > 0) {
        res += n % 10;
        n /= 10;
    }
    return res;
}
void naive(ll n) {
    ll original = n;
    while(1) {
        if(n + 1 > original * 2) {
            print(-1);
            return;
        }
        if(n % keta(n) == 0 and (n + 1) % keta(n + 1) == 0) {
            print(n);
            return;
        }
        n++;
    }
}
void solve() {
    STR(s);
    ll n = ssize(s);
    if(n <= 6) {
        naive(stoll(s));
        return;
    }
    ll x = 0;
    rep(i, 3) x = 10 * x + (s[i] - '0');
    x++;
    while(1) {
        if(keta(x) == 8) {
            cout << x;
            rep(i, n - 3) cout << 0;
            print();
            return;
        }
        x++;
    }
}

int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cout << std::setprecision(16);
    int t = 1;
    rep(_, t) {
        solve();
    }
}