C语言 勒让德符号计算

勒让德符号通常表示为 (a/b)，其中 a 和 b 都是整数，a 和 b 在模 b 意义下互质，且

(a/b) = {
1，若存在整数 x 使得 a ≡ x² (mod b)
-1，若不存在整数 x 使得 a ≡ x² (mod b)
}

在 C 语言中，可以使用以下代码实现勒让德符号的计算：

int legendre(int a, int p) {
int res = 1;
a %= p;
if (a == 0) {
return 0;
}
if (a == 1) {
return res;
}
while (a > 1) {
if (a % 2 == 0) {
res = ((p * p) - 1) / 8 % 2 == 0 ? res : -res;
a /= 2;
} else {
res = ((a - 1) * (p - 1)) / 4 % 2 == 0 ? res : -res;
int temp = a;
a = p % a;
p = temp;
}
}
return res;
}