フォルシアゆるふわ競プロオンサイト #3 G - Digit Sum Multiple locked

12 が 4 の倍数で、112 が 8 の倍数だから、1112 が 16 の倍数なんじゃないの...と迷走したりしていた。

問題へのリンク

問題概要

以下の条件を満たす整数 を 1 つ求めよ (というクエリに 回答えよ)

• 桁の整数である
• どの位の値も 0 ではない
• 各桁の話を としたとき、 は の倍数である

制約

• 
• 
• 各クエリの の総和は 以下

考えたこと

こんなことを考えてた

• 上手な を見つけられないか
• 桁についての答えから 桁についての答えが得られないか

しかし後半の方向性は頓挫した。前半の方向性で思ったのは

• が 2 の冪乗になるようにすればよさそう

ということだった。たとえば のときとか、 となることを狙うとすると...16 の倍数であるための必要十分条件は下四桁が 16 の倍数であることなので、下四桁をたとえば 2112 とかにすればよい。残りの 5 桁分で 総和を 10 にすればよいのでたとえば

111162112

とかが条件を満たす。

こんな感じで を適切に定めて を の形になるようにしておいて、下 桁を の倍数となるようにしておけば、構築ができることがわかった。

k 桁の数であって 2^k の倍数であるもの

これを構築するところで迷走していた。

• k = 2 のとき、12 (4 の倍数)
• k = 3 のとき、112 (8 の倍数)
• k = 4 のとき、2112 (16 の倍数)
• ...

という感じなのだが、なんかうまいこと規則が見つからないか...と思ったけどよくわからないことになっていた。ただ、1 と 2 だけで作れることは、数学的帰納法によって比較的簡単に証明できる。

桁の数であって の倍数であるような整数 があったとする。

• が の倍数でもあるとき： の先頭に 2 を付け加えれば OK ( が の倍数であるため)
• が の倍数であって の倍数ではないとき： の先頭に 1 を付け加えれば OK

後半については、

より示される。具体的には とかのときは

11211111212122112

が条件を満たす模様。

#include <bits/stdc++.h>
using namespace std;

vector<long long> two, ten, simo;
void pre() {
    two.assign(19, 1), ten.assign(19, 1); simo.assign(19, 2);
    for (int i = 1; i < 19; ++i) two[i] = two[i-1] * 2, ten[i] = ten[i-1] * 10;
    for (int k = 2; k < 19; ++k) {
        if (simo[k-1] % two[k] == 0) simo[k] = ten[k-1]*2 + simo[k-1];
        else simo[k] = ten[k-1] + simo[k-1];
    }
}

string tostr(long long val) {
    stringstream ss;
    ss << val;
    return ss.str();
}

vector<string> smallans = {"0", "2", "12", "112", "2112", "12345"}; 
string solve(int M) {
    if (M <= 5) return smallans[M];
    int K = 0;
    long long wa = 1;
    while (wa <= M * 2) ++K, wa *= 2;
    string res = tostr(simo[K]);
    reverse(res.begin(), res.end());

    int simowa = 0;
    for (auto c : res) simowa += c - '0';
    int rem_wa = wa - simowa;
    int rem_digit = M - K;
    while (rem_digit--) {
        int add = 1;
        if (rem_wa > rem_digit) {
            add = min(9, rem_wa - rem_digit);
            res += (char)('0' + add);
        }
        else res += (char)('0' + add);
        rem_wa -= add;
    }
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    pre();
    int T; cin >> T;
    while (T--) {
        int M; cin >> M;
        cout << solve(M) << endl;
    }
}