Spoiler tag
Difference between en1 and en2, changed 93 character(s)
is here! Finally, solutions can be spoilered!↵

For example, my solution to F from [contest:645]:↵





<spoiler summary="We need LaTeX in spoilers, too.">↵

![ ](http://www.lurkmore.com/w/images/thumb/0/09/Duckroll.jpg/300px-Duckroll.jpg)↵





<spoiler summary="Okay, seriously now.">↵

The first observation is that for a fixed set of species, the max. number of farms is the GCD of their a_i (we can say c_j=a_{N+j}). So we want the sum of GCDs over all K-element subsets. ↵

The second observation is that this sum for the first x+1 species = sum for the first x species + number of K-1-element subsets containing the x-th species. In order to recalculate it, we only need to find out the number of K-1-element subsets such that their numbers and a_x have GCD equal to g for each divisors g of a_x (obviously, that GCD can't be a non-divisor of a_x); let's call the number of such subsets for given x p(g), then the answer in step x+1 = answer in step x + sum gp(g).↵

It's much easier to calculate the number of K-1-element subsets whose GCD is a multiple of g; let's call that number P(g). We'll get to that later, it's more important to show how to get p-s from P-s.↵

We'll calculate p-s in the order of decreasing g. At first, let's take p(g)=P(g); we need to subtract the subsets whose GCD is strictly bigger than g and a multiple of g. Since we calculated p(g') for all g' > g already, we can just subtract all p(g') such that g' > g is a multiple of g. However, we need to list divisors for all numbers anyway, so it's simpler to subtract p(g') from all p-s of proper divisors of g' right after calculating it.↵

The time complexity of this is O(number of pairs g | g' | a_x). The maximum number of such pairs can be found easily if we know divisor lists; it's 8505 for a_x <= 10^6. We don't need any modulos there, so that's manageable.↵

Now to computing P(g). If there are M_g species with numbers divisible by g, then P(g)={M_g over K-1}. Since M <= N+Q, we can precompute factorials and their modular inverses, which allows us to compute P(g) in O(1) time.↵

Computing M_g is very similar to p-s from P-s: when the number of species with f flowers (an analogy of P) increases by 1, M_d for all d|f (which is an analogy of p) increases by 1.↵

We also need divisor lists; for them, we can use a simplified sieve of Erathostenes. There are O(Alog{A}) divisors, where A=10^6 and the maximum number of divisors of one number <= A is D ~ 300, which means the total time complexity is O((N+Q)(D+8500)+Alog{A}), where the constant next to D is larger than the one next to 8500 due to modulos and more stuff to compute.↵

This may be too slow; to speed it up, we can use the fact that we don't need online processing for the first N added flowers.↵

</spoiler>↵





</spoiler>↵



UPD: Hell yeah, finals! I'll just leave [this](http://webm.host/ef6c0/) here.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Xellos 2016-03-19 00:58:28 93
en1 English Xellos 2016-03-18 22:44:22 2809 Initial revision (published)