本题核心是求解最大公约数等于原数组整体 GCD 的子集数量，首先将数组所有元素除以整体 GCD，把问题等价转化为求新数组中最大公约数为 1 的非空子集数；直接枚举子集无法实现，因此采用倍数筛统计每个约数的倍数元素个数，利用 2 的幂快速计算对应非空子集总数，再从大到小倒序遍历，通过容斥原理剔除最大公约数更大的子集，最终得到恰好以 1 为最大公约数的子集数量，即为所求答案

import java.io.*;
import java.util.*;

public class Main {
    static final int MOD = 1000000007;
    static final int MAX = 1000000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] a = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }

        // 求整体GCD
        int G = a[0];
        for (int num : a) {
            G = gcd(G, num);
        }

        // 除以G，新数组gcd为1
        int[] freq = new int[MAX + 1];
        for (int num : a) {
            int x = num / G;
            freq[x]++;
        }

        // 统计每个d的倍数个数
        int[] cnt = new int[MAX + 1];
        for (int d = 1; d <= MAX; d++) {
            for (int multiple = d; multiple <= MAX; multiple += d) {
                cnt[d] += freq[multiple];
            }
        }

        // 预处理2的幂次
        long[] pow2 = new long[n + 1];
        pow2[0] = 1;
        for (int i = 1; i <= n; i++) {
            pow2[i] = (pow2[i - 1] * 2) % MOD;
        }

        // 从大到小计算f[d]
        long[] f = new long[MAX + 1];
        for (int d = MAX; d >= 1; d--) {
            f[d] = (pow2[cnt[d]] - 1 + MOD) % MOD;//+MOD是为了防止是负数
            for (int k = 2 * d; k <= MAX; k += d) {
                f[d] = (f[d] - f[k] + MOD) % MOD;
            }
        }

        System.out.println(f[1]);
    }

    static int gcd(int a, int b) {//欧几里得算法（辗转相除法）
        return b == 0 ? a : gcd(b, a % b);
    }
}

        // 统计每个d的倍数个数
        int[] cnt = new int[MAX + 1];
        for (int d = 1; d <= MAX; d++) {
            for (int multiple = d; multiple <= MAX; multiple += d) {
                cnt[d] += freq[multiple];
            }

这段代码是数论算法里非常经典的「倍数筛法 / 埃氏筛思想」，核心作用只有一个：

快速统计出：数组中，是数字 d 的倍数的数，总共有多少个。

freq[x]：数组里数字 x 出现的次数

cnt[d]：我们要求的结果 —— 数组中是 d 的倍数的数总个数

为什么要这么写？

因为我们要解决的问题是：求有多少个子集的最大公约数 = 1

而要算这个，必须先知道：有多少个数是 2 的倍数、有多少个数是 3 的倍数、有多少个数是 4 的倍数……

这段代码就是在一次性把所有答案算出来。

        // 从大到小计算f[d]
        long[] f = new long[MAX + 1];
        for (int d = MAX; d >= 1; d--) {
            f[d] = (pow2[cnt[d]] - 1 + MOD) % MOD;//+MOD是为了防止是负数
            for (int k = 2 * d; k <= MAX; k += d) {
                f[d] = (f[d] - f[k] + MOD) % MOD;
            }
        }

这段代码求：恰好以 d 为最大公约数（GCD）的子集数量

cnt[d]：数组里d 的倍数有多少个

pow2[cnt[d]]：这些数能组成的所有子集数量

-1：去掉空集

第二层for：把 “公约数包含 d 但 GCD 比 d 大” 的子集全部减掉，剩下的就是 “恰好 GCD = d” 的子集

例如：

假设数组：[2,4,6]我们求 恰好 GCD = 2 的子集数量

第一步：算所有公约数包含 2 的子集

• 2 的倍数：2,4,6 → 共 3 个

• 子集数 = 2³ - 1 = 7此时 f[2] = 7

第二步：减去 GCD 是 4、6…（2 的倍数）的子集

• 4 的倍数：4 → 子集数 1

• 6 的倍数：6 → 子集数 1

• 其他更大的没有了

所以：f[2] = 7 - 1 - 1 = 5

为什么要从大到小算？

因为：算小的 d 时，必须先知道它所有倍数 k 的 f [k] 值

比如算 d=2 时，必须先算完 d=4,6,8...所以必须从大往小倒着遍历