回分類題庫
h172: E.艾迪摺紙趣
關鍵字: NPSC 2016 高中組決賽

測資點 : 6 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 30 Times / 26 Users | Submit : 148 Times / 56 Users | Accepted rate : 46%
題目加入時間 : 2017-11-03 11:54

Content: 简体中文

艾迪是天龍國小中一個冰雪聰明的孩子。今天學校美術課老師發給同學們一張長方形色紙,讓大家⾃由發揮創意。接過色紙後,艾迪感到無比興奮,因為這是他第一次看到長方形的色紙。於是他把色紙高高的舉在頭上,搖頭晃腦的細細端詳著它的色澤、形狀……。看著看著,好奇的艾迪越發覺得奇怪,臉上露出了十足困惑的神情。

這時,坐在艾迪旁邊的你,看著艾迪詭異的舉動加上疑惑的表情,你決定要一探究竟,看看艾迪腦裡到底在想些什麼。一問之下才發現原來艾迪覺得他⼿裡的這張長方形色紙太不對稱了,不是他所喜歡的正方形,所以他決定要把這張長方形色紙撕成一些正方形的小色紙。

但是艾迪手邊並沒有剪刀、美工刀之類的⼯具,他只能用以下的方式來切割⾊紙:先將手上的色紙沿著和其中一邊平行的方向在任意位置對折,接著沿著折線將整張色紙撕開、一分為二,然後再對這兩張色紙進行上述的操作,一直到剩下的色紙都是正方形的。但是艾迪不希望他的色紙變得太破碎,所以他希望你告訴他以這個方法切割,最少可以把原來的長方形切割成幾個正方形。(注意:艾迪原先拿到的長方形的邊長皆為整數,切出來的正方形邊長也必須為整數)

舉例來說,如果艾迪拿到一張 16 × 22 的長方形色紙,那一種可行的切割方法如下圖所示,最後會得到 6 個正方形,而這個切割方式所切出的正方形數量也是最少的。 

Input:

測試資料第一行有一個正整數 T,代表接下來有幾組測試資料。

每組測試資料只有一行,包含兩個正整數 N, M,代表艾迪的色紙大小為 N × M。

Output:

針對每組測試資料請輸出一行包含一個正整數表示這張色紙最少能切割成幾個正方形。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
3
22 16
3 2
5 35

Sample Output :

6
3
7

Hint :

Author :

NPSC 2016 高中組決賽 (管理員:sagit)

  Solve it!   Status Forum