【数学】到達できない箇所

N段の階段がある（1≦N≦100）
ただし、一回の動作につき階段はA段またはB段ずつ登るとする
（1≦A<B≦5）
この時、N段目を除き、一度も登ることのない段はいくつあるか
（N、A、Bは自然数）

例）N=15 A=3 B=5のとき、登らない段は
1,2,4,7の合計4段

という問題です。


i段目が登れるかどうかというのは、以下のいずれかを満たす時かと思ったのですが、違うとのこと、なぜでしょうか？

①i mod A = 0
②i mod B = 0
③（i mod （A + B）） mod A = 0
④（i mod （A + B）） mod B = 0

No.2 回答者： mtrajcp 回答日時： 2022/05/15 05:47

A=3

B=5
登れる=〇
登れない=×
とすると
2×3+(-1)×5=1…×
4×3+(-2)×5=2…×
1×3+( 0)×5=3…〇
3×3+(-1)×5=4…×
0×3+( 1)×5=5…〇
2×3+( 0)×5=6…〇
4×3+(-1)×5=7…×
1×3+( 1)×5=8…〇
3×3+( 0)×5=9…〇
0×3+( 2)×5=10…〇
2×3+( 1)×5=11…〇
4×3+( 0)×5=12…〇
1×3+( 2)×5=13…〇
3×3+( 1)×5=14…〇
0×3+( 3)×5=15…〇
2×3+( 2)×5=16…〇
4×3+( 1)×5=17…〇

17段目には登れるのに
①17mod3=2≠0
②17mod5=2≠0
③(17mod(3+5))mod3=1≠0
④(17mod(3+5))mod5=1≠0
だからi=17はどれも満たしていないので違います

①imodA=0
②imodB=0
③(i≧A+B)&(imod(GCD(A,B))=0)
と
すれば
A=3
B=5
の場合は
3と5の最大公約数は1だから
すべてのiに対してimod(GCD(3,5))=imod1=0だから
すべてのi≧8に対してi段目は登れる

No.1 回答者： cage64 回答日時： 2022/05/12 13:04

整数xと自然数yについて、x mod y と書いた値は、通常0以上y未満の整数だからです（数学記号ではなくて、計算機の剰余を取る演算ですよね？）。

A=3,B=5, N=27, i=26とします。
2x3+4x5=26 だから、26段目には登れます。
i mod (A+B)=26 mod 8=2 ですので、

1. 26 mod 3=2
2. 26 mod 5=1
3. (26 mod 8) mod 3=2
4. (26 mod 8) mod 5=2
だから、i=26はどれも満たしません。

なお、26 mod 8=10 とできれば、10 mod 5=0でOKです。こういう場合をきちんと表現できてないからダメなのです。