建構一個有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 3
0 1 2 3 4 5
Subtasks:
N<=10 10%
N<=1000 30%
無限制 60%
感謝rsabcmoi贊助
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」
|