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.