题目大意

给定一个长度为 n (1 ≤ n ≤ 20) 的正整数数组 {a₁, a₂, ..., aₙ}（1 ≤ aᵢ ≤ 100）。我们称一个非空子集 S ⊆ {1, ..., n} 为「亲密组」，当且仅当 ∏(i ∈ S) aᵢ 是一个完全平方数。求满足条件的子集个数。

通用思路

1. 质因数幂次取模 2 将每个数 aᵢ = ∏(j) pⱼ^(eᵢⱼ) 分解为质因数的形式，其中 pⱼ 为素数，eᵢⱼ 为对应指数。由于完全平方数要求每个质因子的指数都是偶数，我们只需关心 eᵢⱼ mod 2 ∈ {0, 1}。 用一个二进制掩码（mask）记录每个质因子的奇偶性：第 j 位为 1 表示 eᵢⱼ = 1，否则为 0。

2. 子集枚举 + 异或判零 对于任意非空子集 S，其乘积的质因子指数 mod 2 的总和为 ∑(i ∈ S) eᵢⱼ mod 2， 等价于对各元素掩码按位 异或： ⊕(i ∈ S) mask[i]。 若异或结果为 0，则所有质因子的总指数皆为偶数，乘积即为完全平方数。

3. 时间复杂度

   • 预处理掩码：O(n · P · log aᵢ)，其中 P ≈ 25 为 2 ~ 100 内的素数数目。

   • 枚举所有非空子集：O(2ⁿ · n)。当 n ≤ 20 时，2ⁿ ≈ 10⁶，完全可行。

C++

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 读取 n 和数组
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }

    // 生成 2~100 范围内所有素数
    vector<int> primes;
    for(int x = 2; x <= 100; x++){
        bool isP = true;
        for(int d = 2; d*d <= x; d++){
            if(x % d == 0){ isP = false; break; }
        }
        if(isP) primes.push_back(x);
    }

    int P = primes.size();
    // mask[i] 的第 j 位表示 primes[j] 在 a[i] 中的指数 mod 2
    vector<int> mask(n, 0);

    // 计算每个 a[i] 的掩码
    for(int i = 0; i < n; i++){
        int v = a[i];
        for(int j = 0; j < P; j++){
            int cnt = 0;
            while(v % primes[j] == 0){
                v /= primes[j];
                cnt ^= 1;  // 只关心奇偶性
            }
            if(cnt) mask[i] |= (1 << j);
        }
    }

    long long ans = 0;
    int total = 1 << n;
    // 枚举所有非空子集
    for(int bm = 1; bm < total; bm++){
        int x = 0;
        for(int i = 0; i < n; i++){
            if(bm & (1 << i)) x ^= mask[i];
        }
        if(x == 0) ans++;
    }

    cout << ans << "\n";
    return 0;
}

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 读取 n 和数组
        int n = sc.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++){
            a[i] = sc.nextInt();
        }

        // 生成 2~100 范围内所有素数
        List<Integer> primes = new ArrayList<>();
        for(int x = 2; x <= 100; x++){
            boolean isP = true;
            for(int d = 2; d*d <= x; d++){
                if(x % d == 0){ isP = false; break; }
            }
            if(isP) primes.add(x);
        }

        int P = primes.size();
        int[] mask = new int[n]; // mask[i] 存放 a[i] 的质因子奇偶掩码

        // 计算掩码
        for(int i = 0; i < n; i++){
            int v = a[i];
            for(int j = 0; j < P; j++){
                int cnt = 0;
                while(v % primes.get(j) == 0){
                    v /= primes.get(j);
                    cnt ^= 1;
                }
                if(cnt == 1){
                    mask[i] |= (1 << j);
                }
            }
        }

        long ans = 0;
        int total = 1 << n;
        // 枚举子集
        for(int bm = 1; bm < total; bm++){
            int x = 0;
            for(int i = 0; i < n; i++){
                if((bm & (1 << i)) != 0){
                    x ^= mask[i];
                }
            }
            if(x == 0) ans++;
        }

        System.out.println(ans);
    }
}

Python

import sys
input = sys.stdin.readline

# 读取输入
n = int(input().strip())
a = list(map(int, input().split()))

# 生成 2~100 范围内素数列表
primes = []
for x in range(2, 101):
    is_p = True
    for d in range(2, int(x**0.5)+1):
        if x % d == 0:
            is_p = False
            break
    if is_p:
        primes.append(x)

# 计算每个数的掩码
mask = [0]*n
for i, v in enumerate(a):
    value = v
    for j, p in enumerate(primes):
        cnt = 0
        while value % p == 0:
            value //= p
            cnt ^= 1
        if cnt:
            mask[i] |= (1 << j)

# 枚举所有非空子集，统计异或和为 0 的个数
ans = 0
for bm in range(1, 1<<n):
    x = 0
    for i in range(n):
        if bm & (1<<i):
            x ^= mask[i]
    if x == 0:
        ans += 1

print(ans)

题目内容

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

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

输入描述

第一行输入一个正整数 $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]$