TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

99.0% (98/99)

Submission's AC Ratio

72.9% (129/177)

Tags

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 1

9 2
67 23

Sample Output 1

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 (VSS, 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