10831 - Gerg's Cake
Given a and p, can a square cake be divided into a + n * p equal sized pieces?
You have to test whether there is a solution to x2 = a + n * p, where n is an integer. Taking everything modulo p, we get . Now we use a trick to get to Fermat's Little Theorem: we take everything to the power (p - 1) / 2, so we get . So we only have to check whether . If it is, there is a solution and otherwise there isn't. This can easily be calculated in O(logp).
There are a few special cases, for example , p = 1 and p = 2.
1 3 1024 17 2 101 0 1 -1 -1
Yes Yes No Yes