题目链接：uva 10831 - Gerg's Cake
题目大意：给定a和p。p为素数，问说是否存在x，使得x2≡a%p
解题思路：勒让德记号，推断ap−12≡1%p
#include <cstdio> #include <cstring> #include <algorithm> 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; }版权声明：本文博客原创文章。博客，未经同意，不得转载。
转载于:https://www.cnblogs.com/bhlsheji/p/4616145.html
