Editorial for WC '16 Finals S2 - Rational Recipes


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Let's break down our counting of valid recipes by the number of monkeys m which would be served by them. Note that m uniquely determines the value of R_1 – in particular, to satisfy m \times R_1 = F_1, we must have R_1 = \frac{F_1}{m}. This further implies that m must be a divisor of F_1.

This is useful due to the fact that F_1 can't have many different divisors. In fact, we can find all of them by iterating over each integer i between 1 and \lfloor \sqrt{F_1} \rfloor, inclusive. If F_1 \bmod i is equal to 0, then i is a divisor of F_1. Furthermore, \frac{F_1}{i} is also a divisor of i – however, if i = \frac{F_1}{i}, we need to be careful to not count its recipes twice!

Now, for a given value of m, we need to be able to count the number of valid recipes which would serve m monkeys. As shown, there's a single valid value for R_1. Meanwhile, each other R_i (for 2 \le i \le N) can independently be any positive integer such that m \times R_i \le F_i. The number of such valid values is simply equal to \lfloor \frac{F_i}{m} \rfloor. Overall, the number of valid recipes for a given value of m is then the product of these N-1 rounded-down quotients. While computing the running product, we need to be careful to mod it by 10\,007 after every iteration.

The final answer is the sum of the above counts for all of F_1's divisors, again taken modulo 10\,007. The time complexity of this algorithm is \mathcal O(\sqrt{F_1} \times N).


Comments

There are no comments at the moment.