UVa 10831

From Algorithmist
Jump to: navigation, search

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 x2 = 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(logp).

[edit] Gotcha's

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

[edit] Input

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

[edit] Output

Yes
Yes
No
Yes
Personal tools
Namespaces
Variants
Actions
Navigation
Toolbox