Solução Informática – Nível Intermediário – Semana 37

por

Solução escrita por Enzo Dantas

Olhando para as duas variáveis $$a$$ e $$b$$ e tentando limitá-las de alguma forma, percebemos que podemos fazer com que uma delas seja menor ou igual a $$\lceil \sqrt{M} \rceil$$. Defina $$R = \lceil \sqrt{M} \rceil$$ (R de raiz). Se ambas fossem maior que $$R$$, então poderíamos diminuir uma delas e o produto $$a \cdot b$$ ainda seria maior ou igual a $$M$$. Logo, testaremos todos os valores entre 1 e $$R$$ para $$a$$, acharemos o $$b$$ correspondente, ou seja, o menor $$b$$ tal que $$a \cdot b \ge M$$, e, caso $$b \le N$$, salvamos $$a \cdot b$$ como uma possível resposta. Mexendo com a equação temos que $$a = \lceil \frac{M}{b} \rceil$$. Assim, temos:

$$resposta = min(resposta, a \cdot b) $$   $$\forall$$ $$1 \le a \le min(N,R)$$

Recomendamos que você tente implementar o problema antes de ver o código. Veja a implementação nesse link.