玩完填方格遊戲之後,他們終於發現這個遊戲真的很無聊。但是,看著方格上滿滿的數字,忽然他們又有了一個靈感。
於是,他們從所有的數字當中選出了M個正整數(可能重複),依序為$A_0, A_1, \cdots, A_{M-1}$,然後再另外決定一個「特別的數字」C。因為他們算XOR算膩了,他們決定改算乘法。
遊戲規則是這樣的:每一個人都可以隨意從這M個數字當中選K > 0個數自己記錄下來。選出的數必須符合以下條件:
1. 這K個數的編號必須兩兩相異(當然,這些數有可能相等)。
2. 這K個數乘起來必須是「特別的數字」的倍數。
所有人都記錄完自己的數之後,就會決定到底誰贏了這局。
在那些選的數符合條件的人當中,記錄下來的數字最少的人會贏得這局。如果有很多個人記錄下來的數字一樣多,記錄下來的數字加起來的值最小的贏得這局。如果還是有很多個人記錄下來的數字加起來的值一樣,則這些人都贏得了這局。
你也參與了這個遊戲。你希望找出一個一定會贏的選數字方法。
第一行有兩個正整數$M \leq 1000, C \leq 10^ {16}$,分別代表數字數量和「特別的數字」。
第二行有M個正整數,代表$A_0, A_1, \cdots, A_{M-1}$。$A_i\leq 10^ {16}$。
子任務(測資) | 額外限制 | 分數 |
1 (0~1) | $M \leq 20; C, A_i\leq 10^ 4$ | 11 |
2 (0~5) | $M \leq 20$ | 7 |
3 (6~8) | $M \leq 100; C, A_i\leq 10^ 6$ | 23 |
4 (6~13) | $C, A_i\leq 10^ {12}$ | 43 |
5 (0~19) | 無限制 | 16 |
輸出兩行代表一種必勝的選數字方法。
第一行輸出一個整數K代表要選幾個數字;
第二行輸出K個整數代表要選編號為多少的那些數字。
輸出任意一種必勝的選數字方法就可以了,編號可以以任意順序輸出。
如果沒有任何一種符合條件的選數字方法,輸出一行-1。
這題原本要出現在上次的模擬賽的w
2016/10/14 測資修正 by hansonyu123
原本testdata no.4中少一個數字,現已重置且rejudge。感謝Pinkie Pie。
Problem set / Description by Yihda Yol
建國中學105學年度校內第二次模擬賽 pC
題目改編自Codeforces(測資加強)
No. | Testdata Range | Score |
---|---|---|
1 | 0~1 | 11 |
2 | 0~5 | 7 |
3 | 6~8 | 23 |
4 | 6~13 | 43 |
5 | 0~19 | 16 |