Find the Number of Subsequences With Equal GCD solution and explanation

MOD = 10**9 + 7

from math import gcd
def num_subsequences(nums):
    max_num = max(nums)
    count = [0] * (max_num + 1)

    for num in nums:
        count[num] += 1

    result = 0
    for g in range(1, max_num + 1):
        subseq_count = 0

        for multiple in range(g, max_num + 1, g):
            subseq_count += count[multiple]

        if subseq_count > 0:
            result = (result + (pow(2, subseq_count, MOD) - 1) * (pow(2, subseq_count, MOD) - 1)) % MOD

    return result

print(num_subsequences([1, 2, 3, 4])) # Output should be 10

#include <vector>
#include <algorithm>
#include <iostream>

#define MOD 1000000007

using namespace std;

int num_subsequences(vector<int>& nums) {
    int max_num = *max_element(nums.begin(), nums.end());
    vector<int> count(max_num + 1, 0);

    for (int num : nums) {
        count[num]++;
    }

    long result = 0;
    for (int g = 1; g <= max_num; ++g) {
        long subseq_count = 0;

        for (int multiple = g; multiple <= max_num; multiple += g) {
            subseq_count += count[multiple];
        }

        if (subseq_count > 0) {
            long total_subseqs = (long long)(pow(2, subseq_count) - 1 + MOD) % MOD;
            result = (result + (total_subseqs * total_subseqs) % MOD) % MOD;
        }
    }

    return (int)result;
}

int main() {
    vector<int> nums = {1, 2, 3, 4};
    cout << num_subsequences(nums) << endl; // Output should be 10
    return 0;
}

import java.util.*;

public class NumSubsequences {
    public static final int MOD = 1000000007;
    
    public int numSubsequences(int[] nums) {
        int n = nums.length;
        int maxNum = Arrays.stream(nums).max().orElse(0);
        int[] count = new int[maxNum + 1];
        Arrays.fill(count, 0);

        for (int num : nums) {
            count[num]++;
        }

        long result = 0;
        
        for (int g = 1; g <= maxNum; g++) {
            int subseqCount = 0;
            for (int multiple = g; multiple <= maxNum; multiple += g) {
                subseqCount += count[multiple];
            }

            if (subseqCount > 0) {
                long totalSubseqs = (pow(2, subseqCount, MOD) - 1 + MOD) % MOD;
                result = (result + (totalSubseqs * totalSubseqs) % MOD) % MOD;
            }
        }

        return (int) result;
    }

    private long pow(int base, int exp, int mod) {
        long result = 1;
        long power = base;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result = (result * power) % mod;
            }
            power = (power * power) % mod;
            exp >>= 1;
        }
        return result;
    }

    public static void main(String[] args) {
        NumSubsequences sol = new NumSubsequences();
        int[] nums = {1, 2, 3, 4};
        System.out.println(sol.numSubsequences(nums)); // Output should be 10
    }
}