POJ 3992 Tiles of Tetris, NOT!

Time Limit: 1000MS Memory Limit: 65536K

Total Submissions: 408 Accepted: 161

Description

You’ve really messed up this time. “Go buy some square tiles” your supervisor told you. But as usual, you were either busy reading that message, answering that e-email, or updating your wall status on facebook. “Go buy some tiles” was all that you could remember. Your supervisor is now complaining that the tiles you bought were not squares and you’ll be fired if you don’t fix it! 

“Fix it? How am I supposed to fix it?” you say to yourself. “I’m a programmer, The only tiles I know are those of the game Tetris!” There is no way you can afford to be fired either. This is your third job in less than a month. “I have to fix it!” you keep repeating. 

You call the store you bought the tiles from, but they won’t take them back or even exchange. “We cannot cancel orders once the merchandise has left the store”, they tell you. You take a look at the tiles, they’re all rectangle-shaped and all of the same size. You’d be losing a lot if you cut them, not that you’d be able to cut them into perfect squares in the first place. “Wait a minute!” you say to yourself. You grab a bunch of tiles, put them in some arrangement and Voila, that’s a square. But that won’t convince your boss. 

 

 

Tiles are supposed to be small, and what you came-up with is rather big. You take another look at your arrangement, and it hits you again. “I’m on a roll today!” you say proudly to yourself. You just figured out how to find the smallest number of tiles needed to form the smallest possible square. 

You rush and bring your supervisor to show him your discovery. He’s not that much impressed. You’re not 易做图 sense anyway (given all the blood rushing in your head trying to explain your algorithm.) You know that the calculation is definitely much 易做图r than what you’re saying, but you just can’t seem to think clearly. 

 

 

Finally, your supervisor shouts: “First of all, the tiles have to be laid-down in the same orientation. Second, I’m running a construction site here, not a software shop! How do you expect the workers to figure out that number! You either write me a program to do the calculation you’re describing, or you go collect your netbook, your cell, your ipod, and your blackberry, and you get out of here this minute!”

Input

Your program will be tested on one or more data sets. Each test set is described on a single line made of two positive numbers: (0 < W,H < 1,000,000) which are the width and height of each tile. The last line is made of two zeros.

Output

For each test case, write the answer on a separate line. 

Sample Input

2 3

1 2

0 0

Sample Output

6

2

Source

anarc 2009

 

 

题目大意：给定一个矩形长宽，问你至少多少个这样的矩形能拼成正方形。

 

 

解题思路：水题，正方形边长即矩形长宽的最小公倍数.

 

 

#include <iostream>  
using namespace std;  
  
long long 易做图(long long a,long long b){  
    return (b>0)?易做图(b,a%b):a;  
}  
  
long long x,y;  
  
int main(){  
    while(cin>>x>>y && (x||y)){  
        long long lcm=x*y/易做图(x,y);  
        cout<<lcm/x*lcm/y<<endl;  
    }  
    return 0;  
}  

 

补充：软件开发 , C++ ,