题目链接：uva 10831 - Gerg's Cake

题目大意：给定a和p，p为素数，问说是否存在x，使得x2≡a%p

解题思路：勒让德记号，判断ap?12≡1%p

#include 
   
     #include 
    
      #include 
     
       using namespace std; typedef long long ll; ll pow_mod (ll a, ll n, ll mod) { ll ans = 1; while (n) { if (n&1) ans = ans * a % mod; a = a * a % mod; n /= 2; } return ans; } int legendre (ll a, ll p) { a %= p; if (a == 0) return 0; if (pow_mod(a, (p-1)/2, p) == 1) return 1; else return -1; } int main () { ll a, p; while (scanf("%lld%lld", &a, &p) == 2 && a != -1 && p != -1) { if (legendre(a, p) < 0) printf("No\n"); else printf("Yes\n"); } return 0; }