|
uchinyan |
|
スモークマンさんの解法(#27213)を見ていて、「そうそう、これがあったな。」と思い出した解法。
多分、私が高校生のときだったら、こうやっただろうと思います。 文字式使いまくりなので、算数ではないし、スマートでもないですが、 二元一次の不定方程式を地道に解く、と意味で、かなり一般的で応用の利く解法です。 ポイントは、ユークリッドの互除法的なアルゴリズムだけです。 思い出させてくれたスモークマンさんに感謝 ^^/ (解法6) 使用する文字式の値は、整数だけとします。 今、X で、正の整数の最小、という条件だけを除いたものを x とします。すると、 x + 1 = 2a, x + 2 = 3b, x + 6 = 5c, x + 30 = 11d, x + 330 = 41e これを整数の範囲で解けばいいです。 a の式から、 x = 2a - 1 これと b の式から、 3b = (2a - 1) + 2 = 2a + 1 2a = 3b - 1 a = b + (b - 1)/2 両辺が整数になるには、 b = 2p + 1 です。そこで、 x = 6p + 1 これと、c の式から、 5c = (6p + 1) + 6 = 6p + 7 c = p + 1 + (p + 2)/5 両辺が整数になるには、 p = 5q - 2 です。そこで、 x = 30q - 11 これと、d の式から、 11d = (30q - 11) + 30 = 30q + 19 d = 2q + 1 + (8q + 8)/11 両辺が整数になるには、 q = 11r - 1 です。そこで、 x = 330r - 41 これと、e の式から、 41e = (330r - 41) + 330 = 330r + 289 e = 8r + 7 + (8r + 8)/41 両辺が整数になるには、 r = 41s - 1 です。そこで、 x = 330 * 41 * s - 330 - 41 = 13530 * s - 371 になります。 X は、x で x > 0 となる最小のものなので、s = 1 として、 X = 13530 * 1 - 371 = 13159 になります。 スモークマンさんへ。 途中でいろいろと工夫されていますが、むしろ最後まで一般解として解いてしまった方が、スッキリ解けるようです。 |
|
ネコの住む家
4月14日（金） 11:45:26
MAIL:uchi@sco.bekkoame.ne.jp 27217 |