1095 Nikifor-3 †問題: †1,2,3,4が必ず含まれるような10進数が与えられたときに, その順列のなかで, 7で割れるようなものがあればそれを求める問題. 基本解法: †なぜ 1,2,3,4？ --> この順列の10進数に対して, 7で割るとすべての余りが出現. 解法: †1,2,3,4についてはそれぞれ一つを抜きだし, 別に(最後に)考える. 0については, 前にあるとまずいので, 最後に全部くっつける. それ以外の並べかたは？ --> 実は適当でOK. 例えば, 5,3が残っているのなら, まず, 53 % 7 = 4. 1から4の順列を後につけるので, 全体の余り = ( 4 * 10000 % 7 ) + ( 1 から 4 の順列 % 7 )
= 2 + ( 1 から 4 の順列 % 7 )
となる. 上の第二項は好きに選べるのだから, 5にしてしまえば7の倍数になる. 5になるような順列は 1324. よって, 5,3 + 1,3,2,4 と順に出力. (+は見やすくするために追加) プログラム例 † |
1095.matsuzaki.cpp