Hi Codeforces,
I have been trying to solve this problem for quite a while but failed. Any help would be appreciated :)
The problem: Given an array of N integers and Q queries, in each query find number of subsets of size K of the subarray [L, R] such that each subsets' GCD is 1. Answer is modulo 10^9 + 7.
Problem Link
Constraints:
1 ≤ N ≤ 50000
1 ≤ L ≤ R ≤ N
1 ≤ Q ≤ 50000
1 ≤ A[i] ≤ 10000
1 ≤ K ≤ R − L + 1
I have tried with Mobius function and inclusion-exclusion technique but it takes too much time and memory (my code). I guess I will have to use some kind of data structure but can not figure out which one and how? Thank you.
adurysk is the author of the problem may be he can help with this :)