問題

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

考え方

ある数 $N$ を $P$ 進数で表記したときにどのようになるか考えると解ける。つまり $N$ を $P$ 進数で表記したときに下の桁の数から $b_0,b_1,b_2,\cdots,b_M$ で表されたとすると $N=b_0*P^0+b_1*P^1+b_2*P^2+\cdots, +b_M*P^M$ と表すことができる。

$\forall k \in \mathbb{N}, p^k \equiv 1\ (mod\ P-1)$ であるから $N$ について $P-1$ の余りをとると $N=b_0*P^0+b_1*P^1+b_2*P^2+ \cdots +b_M*P^M \equiv b_0+b_1+b_2+ \cdots +b_M\ (mod\ P-1)$ となる。

よって、 $N$ を $P$ 進法で表したときの桁和が $a_p$ であると仮定すると、 $N$ を $P-1$ で割った余りが $a_p$ であることが言える。これは $2 \le P \le 30$ なる $P-1$ を法として、各 $a_p$ に中国剰余定理を適応することができて、そのような $N$ は $LCM(2,\cdots,30) \approx 2.3 * 10^{12} \gt 10^{12}$ であるから $[1,10^{12}]$ に唯一定まる。そのような $N$ が定まったときに仮定の条件を満たしているか確認すればよい。