c - 如何找到可用于平铺矩形纸的最大正方形？

Question

给定一张纸的长度和宽度，我们必须把这张纸分成大小相等的正方形。如果我们将纸切割成这个最大长度的正方形，我们想要找到将它切割成的正方形的数量。

我有以下代码。这段代码正确吗？

main()
{
int t,l,b,i,j,area;
scanf("%d",&t);
int a[t];
for(i=0;i<t;i++)
{
    a[i]=0;
    scanf("%d%d",&l,&b);
    area=l*b;
    for(j=1;j*j<=area;j++)
    {
        if(area%(j*j) ==0)
            a[i]=area/(j*j);
    }
}
for(i=0;i<t;i++)
    printf("%d\n",a[i]);
}

Answer 1

作为提示，如果长度和宽度是整数，那么您可以使用的最大平方大小将由长度和宽度的最大公约数给出，因为平方大小必须除以长度和宽度。尝试使用欧几里得算法来计算他们的 GCD；它非常容易编码并且非常高效。

然后，您可以通过计算确定正方形的数量

length * breadth / gcd(length, breadth)^2

分子是纸的总面积，分母是一平方的总面积。

希望这可以帮助！