TopCoder

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

User's AC Ratio

98.6% (68/69)

Submission's AC Ratio

75.6% (96/127)

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

No. Testdata Range Score
1 0 20
2 1 20
3 2 20
4 3 20
5 4 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5