|
25no12 |
|
#30813ダンディ海野さん
以下、出題者の表記に従って、特に断らない限り2進数で表記、漢数字は十進数とする 明らかに、 十で割り切れる⇔二つの素数二と五で割り切れる・・・（Ａ） 二で割り切れる⇔1の位が0である・・・（Ｂ） 五で割り切れる条件について考える 五の二進数表記は101 1111=101*11より、1111は五の倍数 1+1111=10000より、 10000≡1 (mod 101) よって、ある二進数Ｎについて、 Ｎ’=四の倍数の桁の合計×1000+四で割って三余る桁の合計×100+四で割って二余る桁の合計×10+四で割って一余る桁の合計 とすると、 Ｎ’≡Ｎ (mod 101) さらに、Ｎ-101×n≡Ｎ (mod 101)なので、計算を簡単にするため、Ｎ’の計算に先立ち、飛び石で二つ並んだ1をすべて取り除く（二通り以上の取り除き方がある場合があるが、どちらでもよい） この操作で0となる場合は五の倍数・・・（Ｃ） 計算されたＮ’について、上記操作を繰り返すことにより、五の倍数であるか判定できる （Ｂ）と（Ｃ）から、十の倍数であるか判定する 分かりにくいので、例えば・・・ Ｎ=110010 （十進数の50）のとき、Ｎ’=0×1000+0×100+(1+1)×10+1=101 （Ｃ）の操作で飛び石の1が取り除けて0となるので、五の倍数 また、1の位が0なので（Ｂ）より二の倍数 よって、（Ａ）から、Ｎは十の倍数 dobaさんのやり方はシンプルでいいですね−。 こちらは足し算だけでできるのが「強み」といえるか・・・。 |
|
9月22日（土） 17:22:18
30815 |