內容
建構一個有2N個點的質數圖，其中編號為0到2N-1的整數，編號i和編號j的點有連邊若且維若4N-i-j是質數。我們稱這張圖為質數圖G_N。
現在，你必須求出G_N上最小字典序的最大匹配。
一張圖G邊集的子集E，滿足對所有e1,e2在邊集中且e1不等於e2均有e1和e2沒有公共點，則稱E為G上的一個匹配。
若G上的匹配E，滿足對所有G上的其他匹配E' 都有|E'|<=|E|，則我們稱E為圖G上的最大匹配。
我們將一條邊記為(a,b)，代表這條邊兩端的編號是a,b且a<b。
若兩條邊x=(a,b),y=(c,d)滿足a<c或(a=c且b<d)，則定義x<y。
定義一個邊集的排序S(E)=(e1,e2,...,ek)代表將E中所有邊由小到大排序。(
那們我們說E的字典序比另一個邊集F小若且維若S(E)的字典序比S(F)的字典序小
例如:當N=4時，{(0,3),(1,2),(4,5),(6,7)}的字典序比{(0,3),(1,2),(4,7),(5,6)}小。
輸入說明
輸入第一行有一個正整數$t\left( t\leq 5\right)$，表示一共有$t$筆測資。
接下來每行有一個正整數$N\left( 2\leq N\leq 2345678\right)$。
輸出說明
對每一筆測資，假設$X$為最大匹配的大小，你必須把$G_N$內的邊集輸出，一共輸出$X$行，每行都是兩個正整數$a$ $b$，表示$\left(a,b\right)$在$G_N$中，注意輸出時要將所有邊從小到大排序，且必須有$a<b$(即編號小的頂點在前)
由於有字典序的限制，因此答案是唯一的。
範例輸入
#1
1 3
範例輸出
#1
0 1 2 3 4 5
測資資訊：
記憶體限制：
64
MB
不公開 測資點#0 (10%): 1.0s , <1K
不公開 測資點#1 (30%): 1.0s , <1K
不公開 測資點#2 (30%): 1.0s , <1K
不公開 測資點#3 (30%): 1.0s , <1K
不公開 測資點#0 (10%): 1.0s , <1K
不公開 測資點#1 (30%): 1.0s , <1K
不公開 測資點#2 (30%): 1.0s , <1K
不公開 測資點#3 (30%): 1.0s , <1K
提示 ：
Subtasks:
N<=10 10%
N<=1000 30%
無限制 60%
感謝rsabcmoi贊助
標籤:
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||