けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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

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

問題へのリンク

問題概要

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

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

制約

  •  1 \le T \le 100
  •  1 \le M \le 10^{5}
  • 各クエリの  M の総和は  2 \times 10^{6} 以下

考えたこと

こんなことを考えてた

  • 上手な  s(N) を見つけられないか
  •  M-1 桁についての答えから  M 桁についての答えが得られないか

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

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

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

111162112

とかが条件を満たす。

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

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

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

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

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

 k 桁の数であって  2^{k} の倍数であるような整数  N があったとする。

  •  N 2^{k+1} の倍数でもあるとき:  N の先頭に 2 を付け加えれば OK ( 2 \times 10^{k} 2^{k+1} の倍数であるため)
  •  N 2^{k} の倍数であって  2^{k+1} の倍数ではないとき:  N の先頭に 1 を付け加えれば OK

後半については、

 10^{k} + N ≡ 2^{k} + 2^{k} ≡ 0 ({\rm mod}. 2^{k+1})

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

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;
    }
}