DISCOコンテスト2019 予選 D - チップ・ストーリー ～黄金編～
あるNに対して、Nをb進数で表した時の桁の和をa[b]とおく。a[2]～a[30]までが与えられるので、Nとしてあり得る数として10^12以下のものを求める問題です。
受験数学とかでNが9の倍数かどうかの判定として各桁の和で判定できる、という知識は有名かと思います。一般にNをb進数で表したとき、N = a[b] mod b-1 となります。これは実際にb^nで展開して両者引いて見るとすぐに分かります。
そのため、中国剰余定理を使ってすべてのbに対して N= a[b] mod b-1 の条件を満たす数を1個生成すると(これをXとおきます)、条件を満たす数はある数Yが存在してX + Y*LCM(2, 3, ..., 30) となります。
LCM(2,3,...,30)=2329089562800<10^12 であるため、10^12以下のものを1個見つけたらそれしか答えの候補はありません。見つけたらその数についてa[2]～a[30]の条件を満たすか確認し、OKなら出力します。計算量は無視できるサイズです。
中国剰余定理を知ってるかどうかで参加者の出来が別れたみたいです。
