TopCoder

User's AC Ratio

84.9% (45/53)

Submission's AC Ratio

40.7% (88/216)

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

No. Testdata Range Score
1 0~84 100

Testdata and Limits

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