How to solve ICPC Amritapuri 2015 regional's Coprimes problem?

Revision en2, by shadowfax, 2016-04-12 11:54:05

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.

Tags number theory, inclusion-exclusion

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English shadowfax 2016-04-13 00:14:08 76
en2 English shadowfax 2016-04-12 11:54:05 150 Tiny change: 'straints: \n1 ≤ N ≤ ' -br (published)
en1 English shadowfax 2016-04-12 11:48:25 864 Initial revision (saved to drafts)