shadowfax's blog

By shadowfax, history, 9 years ago, In English

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.

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

adurysk is the author of the problem may be he can help with this :)