UVa 10831

From Algorithmist
Jump to navigation Jump to search

10831 - Gerg's Cake[edit]

Summary[edit]

Given and , can a square cake be divided into equal sized pieces?

Explanation[edit]

You have to test whether there is a solution to , where is an integer. Taking everything modulo , we get . Now we use a trick to get to Fermat's Little Theorem: we take everything to the power , 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 .

Gotcha's[edit]

There are a few special cases, for example , and .

Input[edit]

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

Output[edit]

Yes
Yes
No
Yes