|
uchinyan |
|
#24705：
なるほど。有名な問題なのですか．．． #24706： ＞aとbが互いに素のとき、ma+nbで書けない 最大の整数は、 ＞ m,n＞0 のときは、ab. ＞ m,n≧0 のときは、ab-a-b. ＞でしたね。 きれいな結果ですねぇ。 #24731, #24729： なるほど。私の#24735の(解法１)と同種と思いますが、より算数らしい感じがして、いいですね。 これらは、一般化もできそうな。 7 を a, 5 を b, a > b で、a, b は互いに素、として、一般に、数を b で割った余りを r = 0, ..., b-1 とします。 a と b は互いに素なので、a の倍数を b で割った余りには、すべての r が出現します。 今、0 以上の数で、b で割った余りが r の数を c、その r を余りにもつ a の倍数の最小を c0 とすると、 c = b * m + r、c0 = a * n0 = b * m0 + r、m >= m0 なので、c = c0 + b * (m - m0) = a * n0 + b * (m - m0) となり、m - m0 >= 0 ならば、c は a の倍数と b の倍数の和で書けます。 そこで、c0 の r について見た最大を c0_max とすると、c0_max - r は、必ず、他の c0 で実現されているので、 c0_max から b を引いたものが、a の倍数と b の倍数の和で書けない最大の数になります。 ここで、今は 0 を許しているので、r = 0 の場合の c0 は、a * b ではなくて、0 になります。 つまり、c0_max は、a * (b-1) = a * b - a ですね。したがって、求める数は、a * b - (a + b)。 もし、対象とする数を pa+qb, p > 0, q > 0 に限ったら、#24706の最初の場合、n0 > 0, m > m0 でなければならず、 m = m0 の c0_max が求める数で、r = 0 の c0 = c0_max = a * b です。 |
|
ネコの住む家
3月17日（木） 17:20:53
MAIL:uchi@sco.bekkoame.ne.jp 24736 |