UVA 10831 - Gerg's Cake

题目链接

题意：说白了就是给定a, p。问有没有存在x^2 % p = a的解

思路：求出勒让德标记。推断假设大于等于0，就是有解，小于0无解

代码：

#include <stdio.h>

#include <string.h>

long long a, p;

long long pow_mod(long long x, long long k, long long mod) {

    long long ans = 1;

    while (k) {

	if (k&1) ans = ans * x % mod;

	x = x * x % mod;

	k >>= 1;

    }

    return ans;

}

int lederang(long long a, long long p) {

    a %= p;

    if (a == 0) return 0;

    if (pow_mod(a, (p - 1) / 2, p) == 1) return 1;

    return -1;

}

int main() {

    while (~scanf("%lld%lld", &a, &p) && a != -1) {

	if (lederang(a, p) < 0) printf("No\n");

	else printf("Yes\n");

    }

    return 0;

}