hdu 5640 King's Cake（アナログ）

テーマリンク:http://acm.hdu.edu.cn/showproblem.php?pid=5640
King's Cake
Time Limit：2000/1000 MS（Java/Others）    メモリLimit：65536/65536 K（Java/Others）
Total Submission(s)：528    Acceepted Submission(s)：421
Problem Description
It is the king's birthday before the miitary parade.The ministers prepared a rectangle cake of size 
n×m(1≦n，m≦10000) . The king plans to cut the cake hiself.But he has a strange habit of cutting cakes.Each time，he will cut the rectanle cake into pieces，one of which shoud be a square cake.Since he love squares，he will cut the biggaest square cake.He will continue to that until all the pieces are.Now can you tell him how many pieces he can get whe finishes.
 
Input
The first line contains a number 
T(T≦1000)、the number of the testcases.
For each testcase，the first line and the only line contains two positive numbers 
n，m(1≦n，m≦10000).
 
Output
For each testcase、print a single number as the answer.
 
Sample Input

   
   
   
   

    
    
    
    2
2 3
2 5
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    3
4

hint:
For the first testcase you can divide the into one cake of $2\times2$ , 2 cakes of $1\times 1$
   
   
   
   

 
ソurce
BestCoder Round钻75
 
Recommund
wange 2014   |   We have carefully selected several simiar probles for you:   5644  5643  5642  5641  5639 
n*mのケーキを一つあげると、毎回正方形を一つしか切りません。出力は最大でいくつの正方形に切りますか？
問題を解く構想：最小辺を基礎にして、毎回最小辺のそんなに大きい正方形を切ります。これをもって類推する
詳細はコードを参照してください

#include <iostream>
#include <cstdio>

using namespace std;

int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        int ans=0;
        //int s=n*m;
        while(n!=0&&m!=0)
        {
            //s-=n*n;
            if (m>=n)
                m-=n;
            else
                n-=m;
            ans++;
        }
        //while (n>=m)
        //{
        //    n=-m;
        //    ans++;
        //}
        cout<<ans<<endl;
    }
    return 0;
}