Resolvendo a equação com divisão inteira sem força bruta

Recentemente, uma questão foi levantada na Torradeira , o que me tocou seriamente. Está enraizado em uma tarefa que darei aqui em uma interpretação ligeiramente diferente:

Uma vez que os programadores passaram o projeto no prazo e receberam prêmios. Para comemorar, eles se jogaram em Mon e compraram cerveja com todo o dinheiro. Eles beberam tudo no mesmo dia, e na BT decidiram continuar, mas não havia mais dinheiro sobrando. Então eles entregaram as garrafas, adicionaram o troco de ontem e novamente colocaram tudo em estoque, como ontem. O mesmo foi feito no SR e no Chet. E no PT o dinheiro era exatamente uma garrafa. Pensamento - lembrava o preço de uma garrafa, quanto eles levavam recipientes (os preços eram sem centavos) e ninguém sabia o quanto originalmente era dinheiro. O projeto foi em grande escala, com grandes bônus - então não vale a pena. Qual era o orçamento mínimo em PN para que os eventos se desenvolvessem dessa maneira?

Raciocinar sobre ela da seguinte maneira


Cheguei a uma equação que no resumo se parece com esta (1):

$$

$$x = a (x // b) + c$$

Tentando encontrar uma abordagem sem uma pesquisa exaustiva para resolver essas equações, passei mais de uma hora, mas no final encontrei uma solução realmente maravilhosa , mas as margens do livro são muito estreitas ;)

Sem ilusões sobre superioridade nesta questão, eu só quero compartilhar o prazer recebido no processo. Se alguém souber um método ou nome alternativo para isso, esclareça-me; Exorto aqueles como eu a discutir, e os impacientes, convido-o a seguir um gato.

Considere a equação resultante nesta forma (2):

$$

$$(x-c) / a = x // b$$

como o lado direito pode aceitar apenas valores inteiros, toda a expressão só faz sentido quando o numerador é um múltiplo do denominador no lado esquerdo. A partir disso, é óbvio que x poderia ter valores começando em ce depois em uma etapa a .

Então considerei a equação (1) como duas funções $$$y1 = x$e $$$y2 = a (x // b) + c$. Em que argumento eles se cruzam, essa é a solução. Por exemplo, escolhi pequenos valores dos parâmetros para exibir a imagem da melhor maneira possível. Então, deixe a = 3, b = 7, c = 9.


Devido à natureza passo a passo da segunda função, os gráficos y1 e y2 se cruzam em dois pontos: para x1 = 12 e x2 = 15, mas de acordo com a condição, estamos interessados ​​no primeiro valor, como o menor. Então, para determinar a área de interseção sem uma pesquisa exaustiva, introduzi uma terceira função - é apenas uma linha reta que limita a função y2 de baixo e tem a equação $$$y3 = a / b (x - (b-1)) + c$.

Agora, resta encontrar o ponto de interseção das duas linhas ( y1 e y3 ) e ajustar a resposta da restrição no x desejado. De fato, com base na condição, pode-se levar apenas os valores nos quais a condição do multiplicador do numerador é satisfeita para o denominador na equação (2), ou seja, $$$x = c + na$, onde n é um determinado fator natural. Para isso, resolvemos uma equação simples $$$x = a / b (x - (b-1)) + c$e se a raiz resultante não atender aos nossos requisitos, iremos movê-la para a raiz mais próxima adequada. Como a função auxiliar y3 tem uma inclinação positiva e todos os valores de y2 estão acima dela, a raiz deve sempre ser ajustada para cima. Portanto, no nosso caso, as linhas se cruzam em x = 11,25 (ponto preto no gráfico), e o valor maior mais próximo que satisfaz a condição é 12 (ponto vermelho), que é a resposta.

Como havia uma tag Python na pergunta no Toaster, abaixo darei um script para resolver esse problema usando a função, para encontrar o orçamento do dia atual com base no orçamento do dia seguinte. Aplicamos a função o número necessário de vezes e, voila, obtemos a resposta!

def this_day_budget(next_day_budget): a = bottle_price - tare_return_price b = bottle_price c = next_day_budget x = (a - a*b + b*c)/(b - a) if (x - c) % a: # value does not match the increment x = ((xc)//a + 1) * a + c return x bottle_price = 7 tare_return_price = 4 party_duration_days = 5 last_day_budget = bottle_price for days_to_party_end in range(party_duration_days): if days_to_party_end == 0: current_budget = last_day_budget else: current_budget = this_day_budget(current_budget) print('first day budget was - %d' % current_budget) 

Em vez de uma conclusão:

a tarefa neste exemplo foi determinada como valores de parâmetro $$$a <b <c <x$, e a própria equação $$$x = a (x // b) + c$; a abordagem proposta com pequenas alterações é aplicável em outros casos semelhantes - o objetivo da publicação era apenas descrever o princípio sem derivar uma solução universal para o caso geral - portanto, não julgue rigorosamente (código Python, incl.) e tenha uma boa sexta-feira!