如何找到可用于平铺矩形纸张的最大方块？

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

作为提示,如果长度和宽度是整数,那么您可以使用的最大平方大小将由长度和宽度的最大公约数给出,因为平方大小必须除以长度和宽度.尝试使用Euclid算法计算他们的GCD; 编码非常简单,效率极高.

然后,您可以通过计算确定平方数

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

分子是纸张的总面积,分母是一个正方形的总面积.

希望这可以帮助!