https://beta.atcoder.jp/contests/ddcc2019-qual/tasks/ddcc2018_qual_d
ある秘密の整数$N$が存在して、その整数を2進数から30進数までで表したときの各桁の和が与えられる。$N$としてありうる数が存在すれば1つ出力し、存在しなければ"invalid"と出力せよ。
ある整数$N$を$p$進数で表したとき、その桁和は$N$ mod $p-1$と合同である（たとえば$p=10$のとき、$10^k$ mod $9$はすべて$1$であるから、$N$ mod $9=a\times 10^0+b\times 10^1+c\times 10^2+...$ mod $9=sum_{digit}$ mod $9$）。よって、$p$進数での桁和からmod $p-1$がわかる（逆はわからない）。ここで、中国剰余定理を使えば$N$の候補を生成することができる。与えられた剰余の情報に合致する整数は$1$から LCM$(1,...29)$のなかで一意に定まり（中国剰余定理の要請として、本来は互いに素なものの剰余が与えられる必要があるので、入力の段階で互いに素ではない2つのmodで矛盾があれば$N$の候補がない場合もある）、それにLCMの倍数を足したものも条件を満たす（ただし、LCM$(1,...,29)\gt 10^{12}$であるから、この問題では$N$の候補が2つ以上になることはない）。$N$の候補がわかったら、桁和が実際に与えられたものになっているかどうか調べて、あっていれば出力すればよい。
$p$進数とmod $p-1$の関係性も中国剰余定理も知らなかったので勉強になった。