首页 > 代码库 > uva 10831 - Gerg's Cake(勒让德记号)
uva 10831 - Gerg's Cake(勒让德记号)
题目链接: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;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。