HDU 5640.King's Cake

387


题目




Description



It is the king's birthday before the military parade . The ministers prepared a rectangle cake of size n times m(1le n, m le 10000)2×22×2


Input



The first line contains a number T(T leq 1000), the number of the testcases.

For each testcase, the first line and the only line contains two positive numbers n , m(1le n, m le 10000)1×11×1


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 cakes of


题解



把长方形按照一刀一刀切成正方形,最后求出所有正方形的个数



如图,2*3的长方形,第一刀可以分割成2*2的正方形和1*2的长方形;
第二刀可以分成两个1*1的正方形
即3个正方形

可以看出,对于一个n*m的长方形(n>m),其操作为分成m*m的正方形和(n-m)*m的长方形

提取出相同的操作,写成递归来统计个数

//a长 b宽
int DFS(int a, int b) {
    if (a == b)
        return 1;
    return 1 + DFS(max(a - b, b), min(a - b, b));

}


代码



/*
By:OhYee
Github:OhYee
Email:oyohyee@oyohyee.com
Blog:http://www.cnblogs.com/ohyee/

かしこいかわいい?
エリーチカ!
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;

//a长 b宽
int DFS(int a, int b) {
    if (a == b)
        return 1;
    return 1 + DFS(max(a - b, b), min(a - b, b));

}

void Do() {
    int n, m;
    scanf("%d%d", &n, &m);
    printf("%d\n", DFS(max(m, n), min(m, n)));
}


int main() {
    int T;
    scanf("%d", &T);
    while (T--)
        Do();
    return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论