-2

1 枚の紙の長さと幅を考えると、1 枚の紙を同じ大きさの正方形に分割する必要があります。紙をこの最大長さの正方形に切断した場合に、紙を切り取った正方形の数を見つけたいと考えています。

次のコードがあります。このコードは正しいですか?

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]);
}
4

1 に答える 1

9

ヒントとして、長さと幅が整数の場合、正方形のサイズは長さと幅を分割する必要があるため、使用できる最大の正方形サイズは長さと幅の最大公約数によって与えられます。Euclid のアルゴリズムを使用して GCD を計算してみてください。コーディングは非常に簡単で、非常に効率的です。

次に、計算によって正方形の数を決定できます。

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

分子は紙の総面積、分母は1マスの総面積です。

お役に立てれば！

于 2013-05-31T22:44:08.023 に答える