UVa 10831

From Algorithmist
Jump to: navigation, search

10831 - Gerg's Cake[edit]

Summary[edit]

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

Explanation[edit]

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 x^{2}\equiv a{\pmod  {p}}. Now we use a trick to get to Fermat's Little Theorem: we take everything to the power (p-1)/2, so we get x^{{p-1}}=a^{{(p-1)/2}}\equiv 1{\pmod  {p}}. So we only have to check whether a^{{(p-1)/2}}\equiv 1{\pmod  {p}}. If it is, there is a solution and otherwise there isn't. This can easily be calculated in O(\log {p}).

Gotcha's[edit]

There are a few special cases, for example a\equiv 0{\pmod  {p}}, p=1 and p=2.

Input[edit]

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

Output[edit]

Yes
Yes
No
Yes