#P14950. [uoi2016]拉夫鲁什卡与数组划分

    ID: 14166 传统题 3000ms 256MiB 尝试: 1 已通过: 1 难度: 5 上传者: 标签>CF1800图论二分图数论筛法构造贪心排序

[uoi2016]拉夫鲁什卡与数组划分

题目描述

拉夫鲁什卡是一个认真学习、梦想成为程序员的学生。在最近一节信息学课上,他最喜欢的老师给他出了如下任务。

设 a1,…,aNa_1,\dots,a_N 是一个自然数序列。需要把数列 1,2,3,…,N1,2,3,\dots,N 划分为两个序列:

b1,…,bMb_1,\dots,b_M

和

c1,…,cKc_1,\dots,c_K

使得:

  • 每个整数 1≤r≤N1\le r\le N 恰好属于序列 bb 或序列 cc 之一,因此 M+K=NM+K=N;
  • 对于任意 1≤i,j≤M1\le i,j\le M 且 i≠ji\ne j,数 abia_{b_i} 与 abja_{b_j} 互质;
  • 对于任意 1≤i,j≤K1\le i,j\le K 且 i≠ji\ne j,数 acia_{c_i} 与 acja_{c_j} 互质。

若两个数的最大公约数为 11,称它们互质。满足上述条件的划分称为序列 aia_i 的一个划分。

划分可能不唯一。老师要求拉夫鲁什卡找到一个使序列 bb 的元素数量最大化的划分。如果有多个划分都能最大化 bb 的元素数量,则选择其中 bb 序列字典序最小的一个。

若存在某个 ii,使得 qi<piq_i<p_i,且对所有 j<ij<i 都有 qj=pjq_j=p_j,则称序列 q1,q2,…,qWq_1,q_2,\dots,q_W 的字典序小于序列 p1,p2,…,pWp_1,p_2,\dots,p_W。

输入格式

第一行包含整数 ZZ(1≤Z≤31\le Z\le 3),表示测试数据组数。

接下来给出 ZZ 组测试数据,每组格式如下。

第一行包含整数 NN(1≤N≤1000001\le N\le 100000),表示序列 aa 的元素个数。

第二行包含 NN 个整数 aia_i(1≤ai≤20000001\le a_i\le 2000000)。

输出格式

对于每组测试数据:

  • 如果不存在任何合法划分,输出一行 -1;
  • 否则第一行输出整数 MM,表示序列 bb 的元素个数;第二行输出 MM 个自然数,按升序表示被放入序列 bb 的原序列下标。

数据范围与评分

测试点由 4 个子任务组成:

  1. 24 分:N≤15N\le 15,1≤ai≤20000001\le a_i\le 2000000;
  2. 24 分:N≤1000N\le 1000,1≤ai≤20000001\le a_i\le 2000000;
  3. 30 分:N≤20000N\le 20000,1≤ai≤20000001\le a_i\le 2000000;
  4. 22 分:N≤100000N\le 100000,1≤ai≤20000001\le a_i\le 2000000。

样例

2
5
1 2 3 4 5
5
2 3 4 5 6
4
1 2 3 5 
-1

样例解释

第一组数据中,不能得到一个让 bb 包含全部 1,2,…,N1,2,\dots,N 的划分,因为数 22 和 44 不互质。第二组数据中,不存在任何合法划分。