ABC060-B - Choose Integers を解く(1)

ABC060-B - Choose Integers

Aの倍数を好きなだけ選んでよいので、選んだ数の総和をBで割った余りが

Cになるのかどうかを調べる問題

なんか凄く難しそうな問題が来た。どうやって解けばいいんだ…

というか、好きなだけ選べるんならどんな余りであろうが

出来るんじゃないのか？

出来ない場合ってどんなパターンだろう。 入出力例を見てみるか…

…

出来ないパターン1つ目は

A=2, B=2, C=1 の場合

A=2 の場合は使える数は 2, 4, 6, 8, … と偶数のみ

偶数のみを足し合わせても偶数にしかならない

偶数を 2 で割っても余りは 0 になるだけだ

確かにこのパターンは 余り 1 にはならない

出来ないパターン2つ目は

A=77, B=42, C=36 の場合

これは一見した感じでは、出来るか出来ないかがよくわからない

本当に出来ないのか検証してみたいと思う

A=77 なので 77, 154, 231, 308, … といった数や、それらを足し合わせた数を

使用することができる

ただし、足し合わせた数については考慮する必要はない

というのも、足し合わせた数は結局 Aの倍数になるからだ

（例えば、77 と 154 を足した数である 231 は 結局 77 の倍数になる）

したがって、77, 154, 231, 308, … の数について、42 で割った時の余りが

36 にならないか調べてみる

調査するために以下のようなコードを書いた

調査用コード

A=77
B=42
for i in range(1,101):
  _C=A*i%B
  print(str(A*i)+' を '+str(B)+' で割った余りは '+str(_C))

出力結果を以下に示す

77 を 42 で割った余りは 35

154 を 42 で割った余りは 28

231 を 42 で割った余りは 21

308 を 42 で割った余りは 14

385 を 42 で割った余りは 7

462 を 42 で割った余りは 0

539 を 42 で割った余りは 35

616 を 42 で割った余りは 28

693 を 42 で割った余りは 21

770 を 42 で割った余りは 14

847 を 42 で割った余りは 7

924 を 42 で割った余りは 0

1001 を 42 で割った余りは 35

1078 を 42 で割った余りは 28

1155 を 42 で割った余りは 21

1232 を 42 で割った余りは 14

1309 を 42 で割った余りは 7

1386 を 42 で割った余りは 0

1463 を 42 で割った余りは 35

1540 を 42 で割った余りは 28

1617 を 42 で割った余りは 21

1694 を 42 で割った余りは 14

1771 を 42 で割った余りは 7

1848 を 42 で割った余りは 0

1925 を 42 で割った余りは 35

2002 を 42 で割った余りは 28

2079 を 42 で割った余りは 21

2156 を 42 で割った余りは 14

2233 を 42 で割った余りは 7

2310 を 42 で割った余りは 0

2387 を 42 で割った余りは 35

2464 を 42 で割った余りは 28

2541 を 42 で割った余りは 21

2618 を 42 で割った余りは 14

2695 を 42 で割った余りは 7

2772 を 42 で割った余りは 0

2849 を 42 で割った余りは 35

2926 を 42 で割った余りは 28

3003 を 42 で割った余りは 21

3080 を 42 で割った余りは 14

3157 を 42 で割った余りは 7

3234 を 42 で割った余りは 0

3311 を 42 で割った余りは 35

3388 を 42 で割った余りは 28

3465 を 42 で割った余りは 21

3542 を 42 で割った余りは 14

3619 を 42 で割った余りは 7

3696 を 42 で割った余りは 0

3773 を 42 で割った余りは 35

3850 を 42 で割った余りは 28

3927 を 42 で割った余りは 21

4004 を 42 で割った余りは 14

4081 を 42 で割った余りは 7

4158 を 42 で割った余りは 0

4235 を 42 で割った余りは 35

4312 を 42 で割った余りは 28

4389 を 42 で割った余りは 21

4466 を 42 で割った余りは 14

4543 を 42 で割った余りは 7

4620 を 42 で割った余りは 0

4697 を 42 で割った余りは 35

4774 を 42 で割った余りは 28

4851 を 42 で割った余りは 21

4928 を 42 で割った余りは 14

5005 を 42 で割った余りは 7

5082 を 42 で割った余りは 0

5159 を 42 で割った余りは 35

5236 を 42 で割った余りは 28

5313 を 42 で割った余りは 21

5390 を 42 で割った余りは 14

5467 を 42 で割った余りは 7

5544 を 42 で割った余りは 0

5621 を 42 で割った余りは 35

5698 を 42 で割った余りは 28

5775 を 42 で割った余りは 21

5852 を 42 で割った余りは 14

5929 を 42 で割った余りは 7

6006 を 42 で割った余りは 0

6083 を 42 で割った余りは 35

6160 を 42 で割った余りは 28

6237 を 42 で割った余りは 21

6314 を 42 で割った余りは 14

6391 を 42 で割った余りは 7

6468 を 42 で割った余りは 0

6545 を 42 で割った余りは 35

6622 を 42 で割った余りは 28

6699 を 42 で割った余りは 21

6776 を 42 で割った余りは 14

6853 を 42 で割った余りは 7

6930 を 42 で割った余りは 0

7007 を 42 で割った余りは 35

7084 を 42 で割った余りは 28

7161 を 42 で割った余りは 21

7238 を 42 で割った余りは 14

7315 を 42 で割った余りは 7

7392 を 42 で割った余りは 0

7469 を 42 で割った余りは 35

7546 を 42 で割った余りは 28

7623 を 42 で割った余りは 21

7700 を 42 で割った余りは 14

とりあえず 77 〜 7700 まで調べてみたが

余りが 36 になるパターンは見つからなかった

もっと数を大きくすればあるのでは？ とも思えるが

上記の結果を見てみると、余りの出現パターンがループしていることがわかる

おそらく上記に挙げた以外の余りは出てこないと予想できる

…ひょっとすると、余りの出現パターンは必ずループするのではないか？

条件が途方もない数を範囲に含んでいるので

規則性があることは間違いないはず

この方針で解く方法を考えていきたいと思う

ABC060-B - Choose Integers を解く(2) へ続く