P6472 - 染色(color)

内存限制：256 MB 时间限制：2 S

题面：传统评测方式：文本比较上传者：

提交：0 通过：0

给你一个长度为 n 的序列 a，你需要依次把每个数染成红色或绿色，设 x 等于所有红色的数的乘积，y 等于所有绿色的数的乘积。一种染色方案是好看的当且仅当红色的数和绿色的数都至少有 1 个，并且 x 和 y 的最大公因数等于 1。

两种染色方案不同当且仅当存在一个数 ai 在两种方案里的颜色不同。

请你求出好看的染色方案数的二进制表示。

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

3
1 2 3

样例输入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。

2022 绍兴初中

6472: 染色(color)

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

数据范围与提示

分类标签