Problem B
Gerg’s Cake
Input: Standard Input

Output: Standard Output

Gerg is having a party, and he has invited his friends. p of them have arrived already, but a are running late. To occupy his guests, he tried playing some team games with them, but he found that it was impossible to divide the p guests into any number of equal-sized groups of more than one person.

Luckily, he has a backup plan - a cake that he would like to share between his friends. The cake is in the shape of a square, and Gerg insists on cutting it up into equal-sized square pieces. He wants to reserve one slice for each of the a missing friends, and the rest of the slices have to be divided evenly between the p remaining guests. He does not want any cake himself. Can he do it?

Input

The input will consist of several test cases. Each test case will be given as a non-negative integer a and a positive integer p as specified above, on a line. Both a and p will fit into a 32-bit signed integer. The last line will contain "-1 -1" and should not be processed.

Output

For each test case, output "Yes" if the cake can be fairly divided and "No" otherwise.

Sample Input                               Output for Sample Input

1 3

1024 17

2 101

0 1

-1 -1

Problem setter: Igor Naverniouk

Special Thanks: Derek Kisman

題目描述：

總共有 p 個人來訪，保證 p 是質數。

其中有 a 個人來晚了，現在有一個 x * x 的正方形蛋糕，先將這些分給已經來的人，

剩餘的只能能保證 a 個人能均分即可，問存不存在一個 x。

題目解法：

給數學公式跪了，Legendre Symbol

x^2 = a (mod p), p is an odd prime. // 題目轉換的公式
if exists solution x = c, c^2 = a (mod p) // 如果 x 有解，假設 x = c。
by fermat's little theorem c^(p-1) = 1 (mod p) // c 一定與 p 互質。
(c^2)^((p-1)/2) = 1 (mod p) => satisfy a^((p-1)/2) = 1 (mod p)

#include <stdio.h>
#include <algorithm>
using namespace std;
// x^2 = a (mod p), p is an odd prime.
// if exists solution x = c, c^2 = a (mod p)
// by fermat's little theorem c^(p-1) = 1 (mod p)
// (c^2)^((p-1)/2) = 1 (mod p) => satisfy a^((p-1)/2) = 1 (mod p)
int LegendreSymbol(long long a, long long p) {
    if(a%p == 0)    return 1;
    long long x = 1, y = (p - 1) /2, z = a;
    while(y) {
        if(y&1)
            x = (x * z)%p;
        z = (z * z)%p, y >>= 1;
    }
    return x == 1;
}
int main() {
    long long a, p;
    while(scanf("%lld %lld", &a, &p) == 2 && p > 0) {
        printf("%s\n", LegendreSymbol(a, p) ? "Yes" : "No");
    }
    return 0;
}