Adobe hiring challenge question

general
1

Please suggest me some approach for this problem.

You are given an array A with N elements. Ai represents the ith element of the array. The greatest common divisor (gcd) of two or more integers is the largest positive integer, not including zero, that divides the numbers without a remainder. For example, the gcd of 8 and 12 is 4.
Your task: Print N space-separated integers where the ith integer represents the number of subsets with gcd Ai%1000000007.

Input Format

The first line contains the integer N.
The second line contains N space-separated integers, representing the elements of the array.

Constraints 
1≤N≤106 
1≤Ai≤N
Output Format

Output N space-separated integers. The ith integer represents the number of subsets with gcd Ai%1000000007.
2

It doesn’t seem to be an ungoing Challenge, so here is a hint: try DP, with num[x][k]=number of subsets from A1…Ak for which gcd=x

3

thanks @beroul. i found the article for it now :slight_smile: