UVA 10831 - Gerg's Cake

题目链接

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

思路：求出勒让德标记，判断如果大于等于0，就是有解，小于0无解

代码：

#include 
  
   
#include 
   
     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; }