is here! Finally, solutions can be spoilered!↵
↵
For example, my solution to F from [contest:645]:↵
↵
↵
↵
↵
↵
<spoiler summary="We need LaTeX in spoilers, too.">↵
↵
↵
↵
↵
↵
↵
↵
<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.
↵
For example, my solution to F from [contest:645]:↵
↵
↵
↵
↵
↵
<spoiler summary="We need LaTeX in spoilers, too.">↵
↵
↵
↵
↵
↵
↵
↵
<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.
