atcoder.jp b 進法での表記 N を b 進数に変換するには、それ以上割れなくなるまで繰り返し b で割り、余りを逆順に並び替えます。この結果が、 0 , 1 のみで表される場合に条件を満たすことになります。2進法は、必ず条件を満たします。N進法では 10, N-1進…

atcoder.jp 等比数列の和の公式が使えるか 問題は、 の を求めよというものです。 これは等比数列の和の公式から となり、 を計算すればよいように思えます。 この計算は、 と を求めて掛け合わせる計算になります。 は の逆元で、 を満たす のことです。こ…

atcoder.jp 連結成分を調べたいときは Union-Find 木 Union-Find 木 (「競技プログラミングの鉄則」 9.6 Union-Find 木) の考え方を利用します。 ロープを頂点とみなして、同じグループに属する頂点を木構造で表現することを考えます。Union-Find 木の表現と…