DDCC 2019 予選 D - チップ・ストーリー ～黄金編～ (700)

• 問題

解法

全力で必要条件を列挙していく.
Nのk進数表記が下の桁から n_0, n_1, n_2, .. であったとすると,
N = n_0 + n_1 r¹ + + n_2 r² + ..
a_k = n_0 + n_1 + n_2 + ..
N - a_k = n_1 (r - 1) + n_2 (r² - 1) + n_3 (r³ - 1) で, r^x - 1 は r-1 で割り切れるので N = a_k (mod k-1) となる.

よって拡張Euclidの互除法を用いてmod lcm(2,3,..,30) の元でこれを求めてやり,
明らかに lcm(2,..,30) > 1e12 なので この解が条件を満たしてやるかを確かめてやれば良い.
拡張Euclidの互除法については下を参照.

qiita.com

メモ

思いつかなかったけど,n進数の各桁の和で割と一般的に使えそうな気がした.
後CRT(中国人剰余定理)はそもそも知らなかったので...

コード