User's AC Ratio

85.7% (12/14)

Submission's AC Ratio

58.8% (20/34)

Description

WA 在競程中代表答案錯誤,在某些比賽中可能沒有 TLE、RE 等判定,僅有 WA 代表答案錯誤。如果遇到 WA 就要開始仔細檢查是否有發生低級的錯誤,例如需要 long long 沒有用,或是沒有考慮到某些特殊狀況、邊界測資,也有可能是解法本身錯誤。這次藍在某個 NPSC 寫到了這題:

艾迪表示他很喜歡正方形的葉子,但森林裡面都只有長方形的葉子,
這讓他很傷腦筋,因此,他決定把長方形的葉子切成幾塊正方形的葉子,
他只能⽤以下的方式來切割葉子:

  • 先將⼿上的葉子沿著和其中⼀邊平行的方向在任意位置對折,
  • 接著沿著折線將整片葉子撕開、⼀分為⼆,
  • 然後再對這兩張葉子進行上述的操作,⼀直到剩下的葉子都是正方形的。

但是艾迪不希望他的葉子變得太破碎,所以他希望你告訴他以這個方法切割,
最少可以把原來的長方形切割成幾個正方形。
(注意:原先拿到的長方形的邊長皆為整數,切出來的正方形邊長也必須為整數

舉例來說,如果拿到⼀張 $16\times22$ 的長方形葉子,那其中⼀種可行的切割方法如下圖所示,
最後會得到 $6$ 個正方形,而這個切割方式所切出的正方形數量也是最少的。

Input Format

測試資料只有一行,包含兩個正整數 $N, M$,代表艾迪拿到的葉子大小為 $N\times M$。

  • $1\leq N, M\leq100$
  • $N\neq M$

Output Format

請輸出⼀行包含⼀個正整數表示這片葉子最少能切割成幾個正方形。

Sample Input 1

22 16

Sample Output 1

6

Sample Input 2

3 2

Sample Output 2

3

Sample Input 3

5 35

Sample Output 3

7

Hints

Problem Source

Subtasks

No. Testdata Range Score
1 0~84 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 200 65536 65536 1
1 200 65536 65536 1
2 200 65536 65536 1
3 200 65536 65536 1
4 200 65536 65536 1
5 200 65536 65536 1
6 200 65536 65536 1
7 200 65536 65536 1
8 200 65536 65536 1
9 200 65536 65536 1
10 200 65536 65536 1
11 200 65536 65536 1
12 200 65536 65536 1
13 200 65536 65536 1
14 200 65536 65536 1
15 200 65536 65536 1
16 200 65536 65536 1
17 200 65536 65536 1
18 200 65536 65536 1
19 200 65536 65536 1
20 200 65536 65536 1
21 200 65536 65536 1
22 200 65536 65536 1
23 200 65536 65536 1
24 200 65536 65536 1
25 200 65536 65536 1
26 200 65536 65536 1
27 200 65536 65536 1
28 200 65536 65536 1
29 200 65536 65536 1
30 200 65536 65536 1
31 200 65536 65536 1
32 200 65536 65536 1
33 200 65536 65536 1
34 200 65536 65536 1
35 200 65536 65536 1
36 200 65536 65536 1
37 200 65536 65536 1
38 200 65536 65536 1
39 200 65536 65536 1
40 200 65536 65536 1
41 200 65536 65536 1
42 200 65536 65536 1
43 200 65536 65536 1
44 200 65536 65536 1
45 200 65536 65536 1
46 200 65536 65536 1
47 200 65536 65536 1
48 200 65536 65536 1
49 200 65536 65536 1
50 200 65536 65536 1
51 200 65536 65536 1
52 200 65536 65536 1
53 200 65536 65536 1
54 200 65536 65536 1
55 200 65536 65536 1
56 200 65536 65536 1
57 200 65536 65536 1
58 200 65536 65536 1
59 200 65536 65536 1
60 200 65536 65536 1
61 200 65536 65536 1
62 200 65536 65536 1
63 200 65536 65536 1
64 200 65536 65536 1
65 200 65536 65536 1
66 200 65536 65536 1
67 200 65536 65536 1
68 200 65536 65536 1
69 200 65536 65536 1
70 200 65536 65536 1
71 200 65536 65536 1
72 200 65536 65536 1
73 200 65536 65536 1
74 200 65536 65536 1
75 200 65536 65536 1
76 200 65536 65536 1
77 200 65536 65536 1
78 200 65536 65536 1
79 200 65536 65536 1
80 200 65536 65536 1
81 200 65536 65536 1
82 200 65536 65536 1
83 200 65536 65536 1
84 200 65536 65536 1