Как решить уравнение с div без перебора?

Question

[pepl213]

Есть уравнение типа:
x - 4(x div 7) = 7
Нужно найти минимальное значение x. Желательно без перебора, т.к. 1 <= x <= 2*10^9

Comments

[Дмитрий]

можно ли "уравнение типа" записать в таком виде?
x - a(x div b) = b
и если да, a и b - только целые?

Answer 1

[Дмитрий]

Если 4 и 7 в примере - это два параметра уравнения (a и b, соответственно), принимающие лишь целые положительные значения, то без перебора - запросто:

def solve_equation(a,b):   # x - a(x div b) = b
    if a%1 + b%1 != 0:
        raise ValueError('both variables must have integer values')
    if 0 < a < b: x = a + b
    else: x = None
    return x

В том смысле, что для любых a < b ответ: a + b. Для всех прочих - решение отсутствует.

Comments

[pepl213]

x - a(x div b) = c )) перебираю значения x от c до с^2. Но по скорости не проходит

[Дмитрий]

pepl213, т.е. в примере просто так совпало?.. Неудачный пример, получается.. :(
Т.е., три параметра: a, b и c?

Ладно, заодно уточню:
х - целое натуральное?
a, b и c - целые натуральные?
...или могут быть так же дробные и/или отрицательные?

П.С.: а лучше - сразу исходное условие теста ;)

П.П.С.: а если ты перебором всё-таки пробуешь, то инкремент делай равным "а" - в "а" раз быстрее будет - может, и "проскочишь" :) ...но это так, костылик ((

[pepl213]

Дмитрий, acmp.ru/index.asp?main=task&id_task=78
Бутылки
(Время: 1 сек. Память: 16 Мб Сложность: 48%)

Группа программистов собралась в понедельник и на все свои деньги купила «Sprite» в бутылках емкостью по 0.25 л., не забыв взять сдачу.

Во вторник они сдали пустую посуду, добавили оставшуюся сдачу и вновь купили столько таких же бутылок «Sprite», сколько могли.

Так они действовали до пятницы. В пятницу, сдав посуду и добавив сдачу с четверга, они смогли купить только одну бутылку напитка. При этом денег у них уже не осталось.

Требуется написать программу, определяющую минимальную сумму, которой располагали программисты в понедельник.
Входные данные

Входной файл INPUT.TXT состоит из единственной строки, содержащей два целых числа F (стоимость одной бутылки «Sprite») и P (стоимость одной пустой бутылки из под «Sprite»), разделенных пробелом.

Ограничения: 1 ≤ P < F ≤ 109, начальная сумма не превосходит 2×109.
Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести одно целое число – минимальную сумму, которой располагали программисты в понедельник.

Пример:
7 3
Пт.7
Чт.11
Ср.19
Вт.39
Пн. 83

F,P = map(int,input().split()) #7 3
 
def f(Q, deep):
    if deep == 5:
        return Q
    for x in range(Q, 100*Q):
        if x == Q+ (F-P)*(x//F):
            break
    return f(x,deep+1)
print(f(F,1)) 
# 12 тест не проходит

[Дмитрий]

pepl213, вижу ты обновил вопрос - я не ответил здесь не потому, что "забил" - до сих пор готового решения без перебора нету.

А к вопросу, как ускорить твой код, повторюсь (я писал выше):

П.П.С.: а если ты перебором всё-таки пробуешь, то инкремент делай равным "а" - в "а" раз быстрее будет - может, и "проскочишь" :) ...но это так, костылик ((

for x in range(Q, 100*Q, F-P):
Это на случай, если тогда не заметил - пока других идей нет.

[pepl213]

Дмитрий, не проходит

[Дмитрий]

pepl213, сегодня, когда я ехал в метро домой, на второй день раздумий, я всё же нащупал способ решения твоего уравннения вообще без перебора. Осталось всё проверить и, если будет интересно, могу изложить мой метод в подробностях

[pepl213]

Дмитрий, мне очень интересно

[Дмитрий]

pepl213, постараюсь за выходные оформить - может, даже в виде публикации получится. Спасибо за интересный вопрос!

[Дмитрий]

pepl213, на днях вернулся из поездки и таки-опубликовал статью на Хабр, как и обещал:
Решение уравнения с целочисленным делением без перебора
Так что если понравится, можешь мой ответ отметить решением (в конце концов, всё то, что тебе посоветовали в следующем вопросе, я предлагал здесь ранее)