Minimum Universal Derivative Order
IMC Trading● MediumNEW GRADOAProblem statement
For this exercise, assume the fixed divisor in a polynomial question is generalized to the positive integer divisor supplied as input.
For a polynomial P, write P^(order) for its orderth derivative, not an ordinary power. The value P^(order)(k) is that derivative evaluated at the integer k.
Return the smallest positive integer order such that P^(order)(k) is divisible by divisor for every polynomial with integer coefficients and every integer k.
No particular polynomial is supplied, and polynomial degree is unrestricted. Constant polynomials and negative or zero integer evaluation points are included. Divisibility of zero follows the usual integer definition.
Complete smallestUniversalDerivativeOrder(divisor) and return the exact integer order. The order must remain positive when divisor = 1.
Function
smallestUniversalDerivativeOrder(divisor: int) → intExamples
Example 1
divisor = 2021return = 47The source instance has 2021 = 43 * 47. An order below 47 misses the factor 47 in its factorial, while 47! contains both 43 and 47.
Example 2
divisor = 1return = 1Every integer is divisible by 1. The required derivative order is positive, so its minimum is 1.
Example 3
divisor = 8return = 4Three powers of 2 are needed. 3! = 6 is insufficient, while 4! = 24 is divisible by 8.
Constraints
- For this exercise, assume
1 <= divisor <= 10^6. - The least positive valid order is at most
divisor, so the return value fits a signed 32-bit integer. - Use a wide integer before multiplying factorial residues; a reduced residue times an order can approach
10^12.