| Submit | All submissions | Best solutions | Back to list |
SQREASY - Find the minimum no of squares |
Little Johny is a very playful kid and often he thinks about petty problems he comes across. One day he had a chocolate bar with him. He can eat a chocolate bar if and only if it is in the shape of a square whose edge is a multiple of unit length. Little Johny eats at most one piece of chocolate every day. He wondered what is maximum number of days he can keep eating the given chocolate bar of length L and width W. We all know that the answer is L*W if he eats 1*1 chocolate bar a day but Little Johny being a very greedy kid wants to finish the chocolate bar as soon as possible. Help him by finding the minimum number of days within which he can finish the chocolate bar.
Input
Input will start with an integer T (the number of test cases) followed by T lines containing two integers L and W (L and W are between 1 and 10^7 inclusive.)
Note: width can also be greater than height.
Output
For each test case output the answer in a new line.
Limits
1 <= T <= 1000
1 <= L, W <= 10000000
Example
Input: 3
1 1
8 5
9 4
Output: 1
5
6
| Added by: | Ranjith Mudalaiyar |
| Date: | 2012-05-23 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | own problem |
hide comments
|
2012-05-26 18:34:07 lemarc
mine is performing very less computations but then too its showing TLE.. |
|
|
2012-05-26 17:54:48 Ranjith Mudalaiyar
if the inputs are 1 10000000 you ll be performing 10^7 operations isnt there a better way out |
|
|
2012-05-26 17:37:57 lemarc
getting time limit exceed again and again.. |
|
|
2012-05-26 17:06:59 Ranjith Mudalaiyar
for those who are getting tle try to change your approach and make sure you are not making more than 10^8 computations totally (even in the worst case) |
|
|
2012-05-26 16:41:34 Ranjith Mudalaiyar
those who got accepted resubmit thier solutions for this problem there was a technical issue and the solutions were not judged properly |
RSS