6472: 染色(color)

内存限制:256 MB 时间限制:2 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:0 通过:0

题目描述

给你一个长度为 n 的序列 a,你需要依次把每个数染成红色或绿色,设 x 等于所有红色的数的乘积,y 等于所有绿色的数的乘积。一种染色方案是好看的当且仅当红色的数和绿色的数都至少有 1 个,并且 x 和 y 的最大公因数等于 1。 
两种染色方案不同当且仅当存在一个数 ai 在两种方案里的颜色不同。 
请你求出好看的染色方案数的二进制表示。

输入格式

第一行一个整数n; 
第二行n个整数a1 …… an。 

输出格式

第一行一个整数n; 
第二行n个整数a1 …… an。 

输入样例 复制

3
1 2 3

输出样例 复制

110

数据范围与提示

样例输入2 
4 
19 19 8 10 
样例输出2 
10 
样例1:除了全为绿色或者全为红色,其它均合法,答案为6,二进制表示为110。 
样例2:(绿绿红红)和(红红绿绿)合法,答案为2,二进制表示为10。 
【数据范围】 
对于10%的数据,n≤2; 
对于30%的数据,n≤15,ai≤15; 
对于60%的数据,n≤10^3; 
对于另外10%的数据,ai=1; 
对于另外10%的数据,ai≤2; 
对于所有数据,1≤n≤10^5,1≤ai≤10^6。