如何最小化两个整数，以使它们的乘积小于某个值？

Question

给出两个整数，如何在保持相对比例的同时将它们最小化，以使其乘积小于其他值？

这是正式的问题。实际的问题是这样的：我的宽度/高度像素分辨率包含随机值（任一维的范围从1到8192之间的任何值）。我要调整值对，以使它们的乘积不超过某个像素总数（例如：1000000），并且我需要确保调整后的分辨率的长宽比保持不变（例如：1.7777）。

天真的方法是运行一个循环，在该循环中，我每次都从宽度减去1，调整高度以匹配长宽比，直到其乘积低于阈值。例如：

int wid = 1920;
int hei = 1080;
float aspect = wid / (float)hei;
int maxPixels = 1000000;
while (wid * hei > maxPixels)
{
    wid -= 1;
    hei = wid / aspect;
}

当然，必须针对此问题采用更具分析性的方法吗？

Answer 1

编辑：误读了原始问题。

[表达问题的另一种方式是用W和H是最大的a和b，以便a/b = W/H和a*b < C其中C是您的限制。

为此，找到D = gcd(W,H)或W的最大公约数。通常使用欧几里得算法找到最大的公分母。

设置H和x = W/D，这是具有相同比率的最小解决方案。

要在y = H/D下产生最大值，请从C的不等式开始，其中F将是我们对F*x*F*y <= C和x的比例因子

代数：

y

F^2 <= C/(x*y)

由于我们希望F为整数，并且严格小于上述值，所以>

F <= sqrt(C/(x*y))

这将为您提供新的解决方案F = floor(sqrt(C/(x*y)))和A = x*F，其中B = y*F和A*B < C。

Answer 2

A/B = W/H，但这是代码形式的解释：