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

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.