Tightly Packed

This problem gives us an integer area, and asks us to find the rectangle (integers for sides) which contains at least that much area, with the least amount of excess.

The question to ask is: if we know ONE side of the box (say, the short side), can we determine what the other side of the box should be? It turns out, yes. We can divide n by the short side of the box (rounding up), and figure out the other side of the box. We ensure that this number is not greater than 2x the short side (otherwise, this will not be valid for the short side of the box, since we can't make the box long enough to contain all the items). Then the question is, how do we determine which is the correct short side? Well, we know that the short side of the box must be <= sqrt(n). as n is 10^16, sqrt(n) is 10^8, which is plenty fast.