Santa Claus has some very special reindeer. On land, they're just regular reindeer. But when they fly, things get strange.
They can only fly in polynomial-like fashion. In particular, you need to give them a polynomial in some finite field (i.e., with modulo calculations), whose graph they will then follow. Santa's local mathematician believes that Lagrange interpolation may be a good way to quickly find the correct polynomials for the route.
The first line contains p,n. p corresponds to the prime number that should be used as modulo (i.e., ℤ/pℤ is the finite field, in which we will calculate everything). n is the amount of coordinates that Santa will need to visit.
Here follow n lines - each corresponding to one coordinate in the format x,y, whose meaning should be rather obvious.
The programme should print the Lagrange polynomial that Santa needs to forward to the reindeer to visit all the targets. The polynomial needs to be formatted and sorted like in the example. It should contain no unnecessary coefficients or exponents that are 1 or 0 (i.e., it should be as compact as possible).
29,5 1,17 5,10 19,17 8,27 27,0
12x^4+26x^3+17x^2+24x+25
Please log in to submit a question...
Please log in to submit a solution...