# UVa 10831

From Algorithmist

## Contents |

## [edit] 10831 - Gerg's Cake

## [edit] Summary

Given *a* and *p*, can a square cake be divided into *a* + *n* * *p* equal sized pieces?

## [edit] Explanation

You have to test whether there is a solution to *x*^{2} = *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*(log*p*).

## [edit] Gotcha's

There are a few special cases, for example , *p* = 1 and *p* = 2.

## [edit] Input

1 3 1024 17 2 101 0 1 -1 -1

## [edit] Output

Yes Yes No Yes