TopCoder

User's AC Ratio

81.5% (22/27)

Submission's AC Ratio

44.6% (37/83)

Description

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

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

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

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

Input Format

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

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

Output Format

請輸出一行包含一個正整數表示這張色紙最少能切割成幾個正方形。

Sample Input

Sample Input #1
22 16

Sample Input #2
3 2

Sample Input #3
5 35

Sample Output

Sample Output #1
6

Sample Output #2
3

Sample Output #3
7

Hints

Problem Source

2016 NPSC高中組決賽

Subtasks

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