Most Efficient Way to count all subsets with gcd = i for an array

Given an array A of N integers, where each Ai <= 10^5 . For each number i calculate number of non-empty subsets with gcd = i, where i ∈ [1,10^5]

Can anyone provide their approach along with its time complexity.
Also if possible provide pseudo code, it will be much helpful.

Thank You! :slight_smile:

1 Like

Can u plz give us an example

1 Like

I don’t know any particular examples but it was used in 1-2 problems. I was not able to figure out how they calculated it.

https://www.codechef.com/problems/AMR15B

In editorial of that problem, they have used it but i cannot understand it’s time compelxity as well as procedure. :confused: