WA 在競程中代表答案錯誤,在某些比賽中可能沒有 TLE、RE 等判定,僅有 WA 代表答案錯誤。如果遇到 WA 就要開始仔細檢查是否有發生低級的錯誤,例如需要 long long 沒有用,或是沒有考慮到某些特殊狀況、邊界測資,也有可能是解法本身錯誤。這次藍在某個 NPSC 寫到了這題:
艾迪表示他很喜歡正方形的葉子,但森林裡面都只有長方形的葉子,
這讓他很傷腦筋,因此,他決定把長方形的葉子切成幾塊正方形的葉子,
他只能⽤以下的方式來切割葉子:
但是艾迪不希望他的葉子變得太破碎,所以他希望你告訴他以這個方法切割,
最少可以把原來的長方形切割成幾個正方形。
(注意:原先拿到的長方形的邊長皆為整數,切出來的正方形邊長也必須為整數)
舉例來說,如果拿到⼀張 $16\times22$ 的長方形葉子,那其中⼀種可行的切割方法如下圖所示,
最後會得到 $6$ 個正方形,而這個切割方式所切出的正方形數量也是最少的。
測試資料只有一行,包含兩個正整數 $N, M$,代表艾迪拿到的葉子大小為 $N\times M$。
請輸出⼀行包含⼀個正整數表示這片葉子最少能切割成幾個正方形。
No. | Testdata Range | Score |
---|---|---|
1 | 0~84 | 100 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 200 | 65536 | 65536 | |
1 | 200 | 65536 | 65536 | |
2 | 200 | 65536 | 65536 | |
3 | 200 | 65536 | 65536 | |
4 | 200 | 65536 | 65536 | |
5 | 200 | 65536 | 65536 | |
6 | 200 | 65536 | 65536 | |
7 | 200 | 65536 | 65536 | |
8 | 200 | 65536 | 65536 | |
9 | 200 | 65536 | 65536 | |
10 | 200 | 65536 | 65536 | |
11 | 200 | 65536 | 65536 | |
12 | 200 | 65536 | 65536 | |
13 | 200 | 65536 | 65536 | |
14 | 200 | 65536 | 65536 | |
15 | 200 | 65536 | 65536 | |
16 | 200 | 65536 | 65536 | |
17 | 200 | 65536 | 65536 | |
18 | 200 | 65536 | 65536 | |
19 | 200 | 65536 | 65536 | |
20 | 200 | 65536 | 65536 | |
21 | 200 | 65536 | 65536 | |
22 | 200 | 65536 | 65536 | |
23 | 200 | 65536 | 65536 | |
24 | 200 | 65536 | 65536 | |
25 | 200 | 65536 | 65536 | |
26 | 200 | 65536 | 65536 | |
27 | 200 | 65536 | 65536 | |
28 | 200 | 65536 | 65536 | |
29 | 200 | 65536 | 65536 | |
30 | 200 | 65536 | 65536 | |
31 | 200 | 65536 | 65536 | |
32 | 200 | 65536 | 65536 | |
33 | 200 | 65536 | 65536 | |
34 | 200 | 65536 | 65536 | |
35 | 200 | 65536 | 65536 | |
36 | 200 | 65536 | 65536 | |
37 | 200 | 65536 | 65536 | |
38 | 200 | 65536 | 65536 | |
39 | 200 | 65536 | 65536 | |
40 | 200 | 65536 | 65536 | |
41 | 200 | 65536 | 65536 | |
42 | 200 | 65536 | 65536 | |
43 | 200 | 65536 | 65536 | |
44 | 200 | 65536 | 65536 | |
45 | 200 | 65536 | 65536 | |
46 | 200 | 65536 | 65536 | |
47 | 200 | 65536 | 65536 | |
48 | 200 | 65536 | 65536 | |
49 | 200 | 65536 | 65536 | |
50 | 200 | 65536 | 65536 | |
51 | 200 | 65536 | 65536 | |
52 | 200 | 65536 | 65536 | |
53 | 200 | 65536 | 65536 | |
54 | 200 | 65536 | 65536 | |
55 | 200 | 65536 | 65536 | |
56 | 200 | 65536 | 65536 | |
57 | 200 | 65536 | 65536 | |
58 | 200 | 65536 | 65536 | |
59 | 200 | 65536 | 65536 | |
60 | 200 | 65536 | 65536 | |
61 | 200 | 65536 | 65536 | |
62 | 200 | 65536 | 65536 | |
63 | 200 | 65536 | 65536 | |
64 | 200 | 65536 | 65536 | |
65 | 200 | 65536 | 65536 | |
66 | 200 | 65536 | 65536 | |
67 | 200 | 65536 | 65536 | |
68 | 200 | 65536 | 65536 | |
69 | 200 | 65536 | 65536 | |
70 | 200 | 65536 | 65536 | |
71 | 200 | 65536 | 65536 | |
72 | 200 | 65536 | 65536 | |
73 | 200 | 65536 | 65536 | |
74 | 200 | 65536 | 65536 | |
75 | 200 | 65536 | 65536 | |
76 | 200 | 65536 | 65536 | |
77 | 200 | 65536 | 65536 | |
78 | 200 | 65536 | 65536 | |
79 | 200 | 65536 | 65536 | |
80 | 200 | 65536 | 65536 | |
81 | 200 | 65536 | 65536 | |
82 | 200 | 65536 | 65536 | |
83 | 200 | 65536 | 65536 | |
84 | 200 | 65536 | 65536 |