プロが教えるわが家の防犯対策術!

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

教えて!goo グレード

A 回答 (2件)

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段目は登れる
    • good
    • 0

整数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です。こういう場合をきちんと表現できてないからダメなのです。
    • good
    • 1

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています

教えて!goo グレード

このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング