TopCoder

Thumb giphy  1
實中34th的一個人
要吃巧克力嗎??

User's AC Ratio

98.1% (52/53)

Submission's AC Ratio

75.0% (78/104)

Description

給個矩形,每次取短邊做正方形分割至單位正方形。問可分割成幾個正方形。

舉個例子,有個$9\times 2$的矩形, 分割的心路歷程是 $9\times 2 \rightarrow 7\times 2 \rightarrow 5\times 2 \rightarrow 3\times 2 \rightarrow 2\times 1 \rightarrow 1\times 1$

所以有$4$個$2\times 2$的,和$2$個$1\times 1$的正方形,共六個。

Input Format

給兩個整數代表長方形邊長。輸入數值皆在$2^ {30}$以內。

輸入包含多組測資。

Output Format

輸出一個貌似答案的正整數。

Sample Input

9 2
67 23

Sample Output

6
15

Hints

Problem Source

原TIOJ1285 / 雄中公假社'08 入退社考。Problem Setter:ggm。

Subtasks

For Testdata: 0 ~ 0, Score: 20
For Testdata: 1 ~ 1, Score: 20
For Testdata: 2 ~ 2, Score: 20
For Testdata: 3 ~ 3, Score: 20
For Testdata: 4 ~ 4, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144
3 1000 65536 262144
4 1000 65536 262144