题解

题面描述

给定一个长度为$n$的数组，数组中每个元素为$a_i$。定义一组数为亲密数当且仅当这组数的乘积是一个完全平方数。要求从数组中选出至少一个元素，使得这些选出的元素构成一组亲密数，求所有可能的选取方案数。

思路

题目内容

小红定义一组是亲密数，当且仅当这组数的乘积是完全平方数。

现在小红拿到了一个数组，她希望选出若干个元素(不能一个都不选)使得它们是一组亲密数。小红想知道有多少种选择方案?

输入描述

第一行输入一个正整数 $n$ ，表示数组的长度。

第二行输入 $n$ 个 正整数 $a_1,a_2,...,a_n$，表示数组。

$1≤n≤ 20$

$1 ≤ a_i ≤ 100$

输出描述

输出一个整数，表示有多少种选择方案。

样例1

输入

6
1 2 3 4 5 6

输出

7

说明

一共存在 $7$ 种方案：

选择元素 $[1]$

选择元素 $[4]$

选择元素 $[1,4]$

选择元素 $[2,3,6]$

选择元素 $[1,2,3,6]$

选择元素 $[4, 2, 3, 6]$

选择元素 $[1, 4,2, 3,6]$