數論 - uva 10831 Gerg's cake

UVa 10831 - Gerg's Cake

a, p, p 為質數, 是否存在整數 x , 使得 x^2 = a mod p


勒讓德符號:

設 a, b是兩個非零整數，b 為質數，定義符號: 

當存在某個${\displaystyle X}$，式子${\displaystyle X^{2}\equiv d{\pmod {p}}}$成立時，稱「${\displaystyle d}$是模${\displaystyle p}$的二次剩餘」

當對任意${\displaystyle X}$，${\displaystyle X^{2}\equiv d{\pmod {p}}}$不成立時，稱「${\displaystyle d}$是模${\displaystyle p}$的二次非剩餘」

github-uva 10831

long long pow_mod(long long a, long long n, long long m)
{
 long long ret = 1;

 while (n) {
  if (n&1)
   ret = (ret * a) % m;
  a = (a * a) % m;
  n /= 2;
 }

 return ret;
}

int legendre(long long a, long long p)
{
 a %= p;
 if (!a) return 0;
 if (pow_mod(a, (p-1)/2, p) == 1) return 1;
 return -1;
}