DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選: D - チップ・ストーリー ~黄金編~

https://atcoder.jp/contests/ddcc2019-qual/tasks/ddcc2018_qual_d

問題概要

1以上1012以下の秘密の整数Nがある。Nをi進数で表したときの各桁の数字の和Ai (i = 2〜30) がそれぞれ与えられるので、条件を満たすNが存在するか判定せよ。存在する場合にはそのようなNをひとつ示せ。

解法

まず重要な事実として「整数nを(k-1)で割ったあまりと、nをk進数で表したときの桁和を(k-1)で割ったあまりは等しい」というものがある。つまり N = Ai (mod (i-1)) である。

このように見ると、「いろんな進数でのNの桁和」という情報は「いろんな数でNを割ったときのあまり」の情報として使うことができる。そしてこれは中国剰余定理と非常に似た形をしている。

  • 中国剰余定理: あるひとつの整数nを互いに素ないくつかの数 m1, m2, ..., mk で割ったときのあまりがわかっているとき、nをm1×m2× ... ×mkで割ったときのあまりは一意に定まる。

この定理は解があるよ〜という話しかしていないが、実際に復元する手順についてもいろいろやり方が知られている(人のコードを見る限り競プロでは拡張ユークリッドの互除法を用いて実装するのが一般的っぽい(が、自分はそれをよく理解してないのでググって出てきた手計算での復元方法っぽいやつを実装した http://did2.blog64.fc2.com/blog-entry-86.html))。

さてこの定理を使うためにはmodがすべて互いに素でなければならない。というわけでi=2〜30の中からi-1が素数のものだけを抜き出してきて計算する。すると N の mod (2×3×5×...×29) での値を出すことができる(modは1〜29の中のすべての素数の積)。2×3×5×...×29 がだいたい 6.5*109 くらいで、Nは1012以下という制約があるので、あとはこのmodの条件を満たす数を総当たりして、逐一条件を満たすかをチェックしていけばよい。

感想

中国剰余定理よく知らなくて解説読んだ後放置してたけどこの問題の範囲ではそんなに難しいことが要求されてるわけではなかった 整数論べんきょうしたいですね

コード(D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, core.stdc.string;

void main() {
    auto A = 29.iota.map!(_ => readln.chomp.to!long).array;
    A = 0 ~ A;

    const long[] P = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29];
    const long PP = P.reduce!"a * b";
    long ans = 0;

    foreach (p; P) {
        // x * (PP / p) = A[p] (mod p)
        long x = A[p] * powmod((PP / p % p), p - 2, p) % p;
        ans += x * (PP / p) % PP;
        ans %= PP;
    }

    while (ans <= 10L^^12) {
        if (iota(1, 30).map!(i => digit_sum(ans, i+1) == A[i]).all) {
            ans.writeln;
            return;
        }
        ans += PP;
    }

    writeln("invalid");
}

long digit_sum(long x, long base) {
    long ret = 0;
    while (x > 0) {
        ret += x % base;
        x /= base;
    }
    return ret;
}

long powmod(long a, long x, long m) {
    long ret = 1;
    while (x) {
        if (x % 2) ret = ret * a % m;
        a = a * a % m;
        x /= 2;
    }
    return ret;
}