Подскажите алгоритм

Question

[Алексей Кузьмин]

Необходимо найти максимально возможное число, которое нельзя получить комбинируя два заданных числа, используя операции суммирования. Например заданы числа 2 и 5 — ответ 3, остальные натуральные числа можно получить комбинируя 2 и 5 (21 = 5 + 5 + 5 + 2 + 2 +2). Если ответ — бесконечность — об этом тоже нужно сообщить.
Числа все натуральные.

Comments

[Никита Гусаков]

Интересная задача, уточните пожалуйста условие. Если 100 и 2 — то такое число 101? Очевидно что всегда таким числом будет |a-b| — или я не правильно понял условие?

Answer 1

[mayorovp]

Вот полное решение.

Пусть исходные числа — a и b.
1. Очевидно, если числа не являются взаимно простыми — ответом будет бесконечность.
2. Известно, что любое число m может быть представлено как m = ka+lb при взаимно простых a и b.
Для того, чтобы m не было разложимым, должно выполняться одно из двух условий: k<0 или l<0.

Заметим, что (k+b)a+(l-a)b = ka+lb = (k-b)a+(l+a)b. Отсюда следует, что для неразложимом m должны существовать такие k и l, что k<0, l<a или k<b, l<0 (иначе можно будет найти разложение по одной из этих формул).
Поскольку нам известны ограничения сверху как для k, так и для l, притом эти ограничения независимы,
можно взять эти переменные по-максимуму.
m = (-1)a+(a-1)b = (b-1)a+(-1)b = ab-a-b.

Следовательно, для взаимно простых a и b ответом будет ab-a-b, а для имеющих общие делители — бесконечность.

Comments

[Алексей Кузьмин]

Отлично, огромное спасибо.

[Владимир Голованов]

Толково :-)

Answer 2

[FilimoniC]

Как обычно 2 пути — Тупой перебор и функциональный анализ.
Думаю, что вам нужно составить систему простых уравнений

Comments

[Алексей Кузьмин]

Тупой перебор то я сразу отмел — так не интересно, по пути анализа пошел, думал пару часиков и додумался только до того что ответ не бесконечность только в том случае, когда одно из чисел четное, а другое — нет.

[fader44]

Числа 3 и 6 — четное и нечетное, а ответ — бесконечность =)

[FilimoniC]

XHellKern: Ну все зависит от задачи. Если вам это одноразово, то и простой перебор подойдет
fader44: почему? Одно из возможных как минимум 8, если считать что множители целые положительные (а при суммировании множитель всегда положителен)

[fader44]

FilimoniC, потому что надо найти максимальное.

[FilimoniC]

мне кажется, максимум тут будет где-то в пределе 20-35.
Кстати вот вариант перебора, наверное, как только мы смогли разложить подряд N чисел, считать что далее возможны любые. Осталось подумать над N. Думаю что это будет 10 или 11.

[fader44]

FilimoniC, ниже написано полное решение задачи. Для чисел 3 и 6 — ответ бесконечность, потому что складывая их мы не получим никаких числел не делящихся на 3.

Answer 3

[fader44]

Бесконечность будет когда они не взаимно просты, во всех остальных случаях ответ конечен. Дальше гуглите диофантовы уравнения, я точного решения до того как усну не выведу =)

Comments

[fader44]

UPD: Тут вроде ближе к концу есть то что надо fm2577.narod.ru/olimp/zicl.doc

[VladX]

Нет. Это разные задачи. В вашем случае коэффициенты могут быть отрицательными, а у автора не могут.

[Алексей Кузьмин]

Отлично, главное дорогу показал — дальше сам прочитаю и выведу алгоритм. Спасибо.

[fader44]

Задачи очень похожи.
Вот вам верхняя оценка на ответ: пусть a<=b, тогда начиная с числа (a-1)*b все числа можно получить. Доказательство(кратко): нам хочется уметь получать все остатки при делении на a, тогда мы сможем добавляя сколько то раз a получать любое число больше. берем числа 0, b, b * 2, b * 3,…, b * (a — 1) в этой последовательности есть все остатки при делении на a (т.к. НОД(а, b) = 1).

[fader44]

И в догонку улучшение верхней оценки (и вроде как точный ответ): т.к. перед b * (a — 1) мы имеем все остатки кроме последнего, предыдущие a — 1 чисел мы получить можем. А значит максимальное число которое может быть недостижимо = (a — 1) * b — a. И это похоже ответ на задачу.

[VladX]

Да. Только нужно аккуратно обработать случай a>b (просто поменять местами), и когда GCD(a,b)!=1, и когда a или b равны 1 (в этом случае тоже бесконечность).

[fader44]

Ну про допущение a<=b я написал в первом комментарии, про GCD там же (дальше предполагал, что числа взаимно просты). В случае одного числа равного 1 тоже все ок — ответ -1, т.к. все числа начиная с 0 мы можем получить.

[VladX]

Затупил. (a-1)*b-a = ab — a — b, т.е. симметрично, поэтому допущение a<=b и не нужно. И с единицей я тоже затупил.

Answer 4

[onehell]

Сам ответить не смогу (я — прикладной программист, а не математик).
Если честно: тебе это нужно для каких-то практических задач?

Comments

[Алексей Кузьмин]

Нет, в практических целях мне искомый алгоритм не понадобится — товарищ подкинул задачку и мне прям интересно стало, но через некоторое время я сдался.

Answer 5

[FilimoniC]

По условию, оба числа обязаны присутствовать в выражении минимум 1 раз?
изначальная система уравнений такая?
aX + bY > Z
a Э [1;+inf]
b Э [1;+inf]
X > 0
Y > 0
X = *
Y = *

По-моему, тут простой матан, хотя у меня из образования только школа — не смогу решить.