ax+by<=N

[AndreyXYZ]

Вступление
Мелкий госслужащий Виктор Воровский с детства питал нездоровую страсть к разного рода заимствованиям. Но одно дело - цивилизованно приватизировать государственные заводы, алмазные месторождения и нефтяные вышки стоимостью в миллиарды долларов. И совсем другое - умыкнуть немного денег из тощего регионального бюджета. У нас с этим строго. Вот и Виктор, едва вытащив руку из государственного кармана, сразу понял, что правосудие не дремлет. Как же уйти от неотвратимого наказания?
Г-н Воровский где-то слышал, что, согласно нормам уголовного законодательства, за растрату дают условный срок, а за кражу - вполне реальный. Следовательно, если часть украденных денег растратить, то продолжительность пребывания за колючей проволокой можно сократить.
Задача
В тот же вечер г-н Воровский ввалился в супермаркет "МегаАпрель" и кинулся к переполненным витринам, сжимая в руках заветный кошелёк с N честно украденными рублями. Оказалось, что в магазине в неограниченном количестве продаются различные товары - качественные и по доступной цене. Качественные товары продаются по цене A рублей за штуку, а товары по доступной цене - по B рублей за штуку. Виктору необходимо растратить как можно больше украденных денег и тем самым максимально сократить продолжительность отбытия справедливого наказания.
Исходные данные
Единственная строка содержит целые числа $A$, $B$ и $N$ ($1 \le A, B, N \le 2\,000\,000\,000$).
Результат
Вывести через пробел количество качественных товаров и количество товаров по доступной цене, покупка которых обеспечит Виктору минимальный срок пребывания за решёткой. Если задача имеет несколько решений, то вывести любое из них.
Пример
исходные данные
8 5 22
результат
2 1
Автор задачи: Никита Рыбак, Илья Гребнов, Дмитрий Ковалёв
Источник задачи: Timus Top Coders: First Challenge
Задача с сайта http://acm.timus.ru/. Довольно сложная. Решили только $11\%$ из тех, кто предпринимал попытки.

На первый взгляд задача мне показалась простой. Пытался решить перебором, предварительно положив $N:=(N \mod AB)+AB$, если $N>AB$. Но на 36-м тесте возникает ошибка: неверный ответ.

[vlad239]

Применим Ваше решение к $5,7,37$. Оно сведет $37$ к $2$ и остаток денег будет 2. В то же время $37=5\cdot 6+7$.

Правильно будет брать по модулю при $N>2ab-a-b$.

Кроме того, возможны ошибки при вычислениях. Как Вы считаете $AB$? Если просто произведением, то на тесте типа $65537,65537,10000000$ получите ошибку. Следует сначала прикидывать величину произведения (например, вычисляя логарифмы).

Влад.

[AndreyXYZ]

vlad239 в сообщении #197348 писал(а):

Правильно будет брать по модулю при $N>2ab-a-b$.

Я удивлен, но задача принята. Можете это доказать?

[maxal]

AndreyXYZ
см. http://en.wikipedia.org/wiki/Frobenius_number

[VAL]

maxal писал(а):

AndreyXYZ
см. http://en.wikipedia.org/wiki/Frobenius_number

А еще можно вот тутпосмотреть: http://www.fizmat.vspu.ru/konkurs/ans37.htm