# UVa 10831

Jump to navigation Jump to search

## Summary

Given ${\displaystyle a}$ and ${\displaystyle p}$, can a square cake be divided into ${\displaystyle a+n*p}$ equal sized pieces?

## Explanation

You have to test whether there is a solution to ${\displaystyle x^{2}=a+n*p}$, where ${\displaystyle n}$ is an integer. Taking everything modulo ${\displaystyle p}$, we get ${\displaystyle x^{2}\equiv a{\pmod {p}}}$. Now we use a trick to get to Fermat's Little Theorem: we take everything to the power ${\displaystyle (p-1)/2}$, so we get ${\displaystyle x^{p-1}=a^{(p-1)/2}\equiv 1{\pmod {p}}}$. So we only have to check whether ${\displaystyle 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 ${\displaystyle O(\log {p})}$.

## Gotcha's

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

## Input

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


## Output

Yes
Yes
No
Yes