有一天,天氣很好!
今天老師教小明最大公因數,所以出了一個與最大公因數(Greatest Common Divisor, 簡稱 gcd)相關的作業。
現在你有 $N$ 個數字 $1\sim N$ ($1\leq N \leq 10^ 5$),老師希望小明把數字分成兩組集合 $S_1$ and $S_2$,使得集合 $S_1$ 的和與集合 $S_2$ 的和的最大公因數 $> 1$。
$$
\gcd(sum(S_1), sum(S_2)) > 1
$$
數字 $1\sim N$,對於每一個數字來說只有兩個可能,屬於集合 $S_1$,或是屬於集合 $S_2$。
小明叫你幫他做,他就請你吃快樂肥宅餐!
第一行有一個整數 $N$($1 \leq N \leq 10^ 5$)
如果辦不到,就輸出 No
,輸出到此結束。
如果你找到了,輸出總共 $4$ 行,
第一行輸出 Yes
第二行輸出兩個整數, $S_1$ 的個數與 $S_2$ 的個數。
第三行輸出屬於 $S_1$ 的數字。
第四行輸出屬於 $S_2$ 的數字。
如果有多種分類方法可以成功,任意輸出一種。
在第一個範例中,我們沒辦法成功,所以輸出 No
。
第二個範例中,我們可以把數字分成1,3
與2
兩組,
使得 $\gcd(4,2) = 2 > 1$
No. | Testdata Range | Score |
---|---|---|
1 | 0~11 | 100 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1000 | 65536 | 65536 | |
1 | 1000 | 65536 | 65536 | |
2 | 1000 | 65536 | 65536 | |
3 | 1000 | 65536 | 65536 | |
4 | 1000 | 65536 | 65536 | |
5 | 1000 | 65536 | 65536 | |
6 | 1000 | 65536 | 65536 | |
7 | 1000 | 65536 | 65536 | |
8 | 1000 | 65536 | 65536 | |
9 | 1000 | 65536 | 65536 | |
10 | 1000 | 65536 | 65536 | |
11 | 1000 | 65536 | 65536 |