TopCoder

$(pr)^3pony$
https://prprprpony.github.io/blog/ $\\\huge PinkiePie:"OkieDokieLokie"$

User's AC Ratio

18.2% (2/11)

Submission's AC Ratio

2.2% (2/92)

Tags

Description

玩完填方格遊戲之後,他們終於發現這個遊戲真的很無聊。但是,看著方格上滿滿的數字,忽然他們又有了一個靈感。

於是,他們從所有的數字當中選出了M個正整數(可能重複),依序為$A_0, A_1, \cdots, A_{M-1}$,然後再另外決定一個「特別的數字」C。因為他們算XOR算膩了,他們決定改算乘法。

遊戲規則是這樣的:每一個人都可以隨意從這M個數字當中選K > 0個數自己記錄下來。選出的數必須符合以下條件:
1. 這K個數的編號必須兩兩相異(當然,這些數有可能相等)。
2. 這K個數乘起來必須是「特別的數字」的倍數。

所有人都記錄完自己的數之後,就會決定到底誰贏了這局。
在那些選的數符合條件的人當中,記錄下來的數字最少的人會贏得這局。如果有很多個人記錄下來的數字一樣多,記錄下來的數字加起來的值最小的贏得這局。如果還是有很多個人記錄下來的數字加起來的值一樣,則這些人都贏得了這局。

你也參與了這個遊戲。你希望找出一個一定會贏的選數字方法。

Input Format

第一行有兩個正整數$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

Output Format

輸出兩行代表一種必勝的選數字方法。
第一行輸出一個整數K代表要選幾個數字;
第二行輸出K個整數代表要選編號為多少的那些數字。

輸出任意一種必勝的選數字方法就可以了,編號可以以任意順序輸出。

如果沒有任何一種符合條件的選數字方法,輸出一行-1。

Sample Input 1

5 60
2 4 6 5 2

Sample Output 1

3
3 0 2

Hints

這題原本要出現在上次的模擬賽的w
2016/10/14 測資修正 by hansonyu123
原本testdata no.4中少一個數字,現已重置且rejudge。感謝Pinkie Pie。

Problem Source

Problem set / Description by Yihda Yol
建國中學105學年度校內第二次模擬賽 pC
題目改編自Codeforces(測資加強)

Subtasks

No. Testdata Range Score
1 0~1 11
2 0~5 7
3 6~8 23
4 6~13 43
5 0~19 16

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 262144 1 2 5
1 1000 262144 262144 1 2 5
2 1000 262144 262144 2 5
3 1000 262144 262144 2 5
4 1000 262144 262144 2 5
5 1000 262144 262144 2 5
6 1000 262144 262144 3 4 5
7 1000 262144 262144 3 4 5
8 1000 262144 262144 3 4 5
9 1500 262144 262144 4 5
10 1200 262144 262144 4 5
11 1000 262144 262144 4 5
12 1000 262144 262144 4 5
13 1000 262144 262144 4 5
14 1800 32768 262144 5
15 1800 32768 262144 5
16 1800 32768 262144 5
17 1000 32768 262144 5
18 1000 32768 262144 5
19 1000 32768 262144 5