NC14420. 方程的解
描述
对于一个模意义下的一元二次方程：x2 + ax + b = 0 (mod p)，其中 p 是质数。
每次给定一组 a,b,p，问这个方程有没有整数解，有解输出“Yes”，无解输出“No”。
有 T 组询问。
输入描述
输入第一行一个正整数T(T<=105)，表示数据组数。
接下来T行每行三个非负整数a,b,p(0<=a,b<p<=109+7)，p是质数，表示一组询问。
输出描述
输出共T行，每行一个字符串“Yes”或“No”分别表示有解和无解。
示例1
输入:
3 4 4 11 38946 243856 19260817 234876 791683756 1000000007
输出:
Yes Yes No
C++14(g++5.4) 解法, 执行用时: 401ms, 内存消耗: 884K, 提交时间: 2019-11-03 18:06:49
#include<iostream>
using namespace std;
long long qpow(long long v,long long t,long long p)
{
long long ret=1;
while(t)
{
if(t&1) ret=ret*v%p;
t>>=1;
v=v*v%p;
}
return ret;
}
int main()
{
ios::sync_with_stdio(false);
int T=0;
cin>>T;
long long a,b,p;
while(T--)
{
cin>>a>>b>>p;
long long A=(a*a-4*b)%p;
if(A<0) A+=p;
if(p==2)
if(b==0||(a+b+1)%2==0) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
else if(A==0||qpow(A,(p-1)>>1,p)!=p-1) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
C++ 解法, 执行用时: 87ms, 内存消耗: 760K, 提交时间: 2022-04-10 19:28:42
#include <cstdio>
using namespace std;
int a,b,p;
int qmi(int di,int zhi)
{
int ret=1,x=di;
while (zhi){
if (zhi&1) ret=1LL*ret*x%p;x=1LL*x*x%p;zhi>>=1;
}return ret;
}
int main()
{
int t;scanf("%d",&t);
while (t--){
scanf("%d%d%d",&a,&b,&p);
if (p==2){
if ((a&1)&&(b&1)) puts("No");
else puts("Yes");continue;
}if (a&1) a+=p;a>>=1;a=(1LL*a*a-b)%p;
if (a==0){
puts("Yes");continue;
}
a=qmi(a,p-1>>1);a=(a+p)%p;
if (a==1) puts("Yes");else puts("No");
}
return 0;
}