Editorial for WC '16 Finals S2 - Rational Recipes
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 which would be served by them. Note that uniquely determines the value of – in particular, to satisfy , we must have . This further implies that must be a divisor of .
This is useful due to the fact that can't have many different divisors. In fact, we can find all of them by iterating over each integer between and , inclusive. If is equal to , then is a divisor of . Furthermore, is also a divisor of – however, if , we need to be careful to not count its recipes twice!
Now, for a given value of , we need to be able to count the number of valid recipes which would serve monkeys. As shown, there's a single valid value for . Meanwhile, each other (for ) can independently be any positive integer such that . The number of such valid values is simply equal to . Overall, the number of valid recipes for a given value of is then the product of these rounded-down quotients. While computing the running product, we need to be careful to mod it by after every iteration.
The final answer is the sum of the above counts for all of 's divisors, again taken modulo . The time complexity of this algorithm is .
Comments