Long Digits Number

2 secs 1024 MB
milkcoffee's icon milkcoffee
Tweet
Problem
Submissions
Test cases
Editorial

この問題では、十六進表記された数における倍数判定を考える必要があります。

十六進表記された整数 XX において、以下のことが成り立ちます。

  • XX の下 11 桁が 22 で割り切れるなら、XX は 22 で割り切れる。(①)
  • XX の各桁の和が 55 で割り切れるなら、XX は 55 で割り切れる。(②)

これら 22 つを同時に満たすとき、 XX は 1010 で割り切れます。

以下は①、②の証明です。
XX を MM 桁として、上からii桁目の数字(文字)を XiX_iとして説明します。
XX は以下のように表せます。

XX == 16M−1X116^{M-1}X_1 ++ 16M−2X216^{M-2}X_2 ++ ... ++ 162XM−216^2X_{M-2} ++ 16XM−116X_{M-1} ++ XMX_{M}

<①について>

XX を下一桁とそれ以外で分けて考えます。

XX == 1616 (16M−2X1(16^{M-2}X_1 ++ 16M−3X216^{M-3}X_2 ++ ... ++ 16XM−216X_{M-2} ++ XM−1)X_{M-1}) ++ XMX_{M}

すると、XX が 22 で割り切れることと XMX_M が 22 で割り切れることは同値であることが分かります。

<②について>

XX を以下のように、各桁の和とそれ以外に分けて考えます。

XX == (16M−1−1)X1(16^{M-1} - 1)X_1 ++ (16M−2−1)X2(16^{M-2}-1)X_2 ++ ... ++ (162−1)XM−2(16^2-1)X_{M-2} ++ (16−1)XM−1(16-1)X_{M-1} ++ (X1+X2+...+XM−2+XM−1+XM)(X_1+X_2+...+X_{M-2}+X_{M-1}+X_{M})

(X1+X2+...+XM−2+XM−1+XM)(X_1+X_2+...+X_{M-2}+X_{M-1}+X_{M}) は各桁の和を表しています。

ここで、16i−116^i-1 (1≤i)(1 \leq i) は 55 で割り切れるため、上の式の左側はすべて 55 で割り切れます。

すると、XX が 55 で割り切れることと (X1+X2+...+XM−2+XM−1+XM)(X_1+X_2+...+X_{M-2}+X_{M-1}+X_{M}) が 55 で割り切れることは同値であることが分かります。

これは 十進表記における、33 の倍数の各桁の和が 33 の倍数であることに似ています。

解答例(C++)

<追加問題>

十六進表記された整数 XX が 1717 の倍数であるかどうかを判定してください。