#P2929. 第1题-小红的亲密数
          
                        
                                    
                      
        
              - 
          
          
                      1000ms
            
          
                      Tried: 38
            Accepted: 10
            Difficulty: 6
            
          
          
          
                       所属公司 : 
                              阿里
                                
            
                        
              时间 :2025年5月7日-阿里淘天(开发岗)
                              
                      
          
 
- 
                        算法标签>暴力枚举          
 
第1题-小红的亲密数
题目大意
给定一个长度为 n (1 ≤ n ≤ 20) 的正整数数组 {a₁, a₂, ..., aₙ}(1 ≤ aᵢ ≤ 100)。我们称一个非空子集 S ⊆ {1, ..., n} 为「亲密组」,当且仅当 ∏(i ∈ S) aᵢ 是一个完全平方数。求满足条件的子集个数。
通用思路
- 
质因数幂次取模 2 将每个数 aᵢ = ∏(j) pⱼ^(eᵢⱼ) 分解为质因数的形式,其中 pⱼ 为素数,eᵢⱼ 为对应指数。由于完全平方数要求每个质因子的指数都是偶数,我们只需关心 eᵢⱼ mod 2 ∈ {0, 1}。 用一个二进制掩码(mask)记录每个质因子的奇偶性:第 j 位为 1 表示 eᵢⱼ = 1,否则为 0。
 - 
子集枚举 + 异或判零 对于任意非空子集 S,其乘积的质因子指数 mod 2 的总和为 ∑(i ∈ S) eᵢⱼ mod 2, 等价于对各元素掩码按位 异或: ⊕(i ∈ S) mask[i]。 若异或结果为 0,则所有质因子的总指数皆为偶数,乘积即为完全平方数。
 - 
时间复杂度
- 
预处理掩码: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 个正整数 a1,a2,…,an,表示数组。
1≤n≤20
1≤ai≤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]