Soluție HackerRank pentru Euler's Criterion, subdomeniul Number Theory, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Euler's Criterion
- Domeniu: Number Theory
- Limbaj: C++14
Challenge: Euler's Criterion
Subdomeniu: Number Theory (number-theory)
Scor cont: 30.0 / 30
Submission status: Accepted
Submission score: 1.0
Submission ID: 464725254
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/eulers-criterion/problem
Cerință
Your friend gives you an equation A equiv X^2 pmod{M} and asks you to find an integer solution for X.
However, you know your friend's mischievous nature and suspect that there is no solution to such an equation. Thus, you first want to find out whether there is a solution to it.
You may find this link helpful: http://mathworld.wolfram.com/EulersCriterion.html
Input Format
The first line contains the number of cases, T. T lines follow, each containing two integers A and M separated by a single space.
Output Format
Output T lines, each containing one word: `YES`, if a solution exists and `NO` otherwise.
Constraints
+ 0 < T ≤ 10^5
+ 2 ≤ M < 10^9, M is prime
+ 0 ≤ A < M
Cod sursă
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ll;
ll power(ll a,ll b,ll m)
{
ll ans=1;
a=a%m;
while(b)
{
if(b&1)
ans=(ans*a)%m;
a=(a*a)%m;
b=b>>1;
}
return (ans%m);
}
int main()
{
ll T,n,M;
cin>>T;
while(T--)
{
cin>>n>>M;
if(n==0)
{
cout<<"YES"<<endl;
continue;
}
if(power(n,(M-1)/2,M)==1)
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}
}
}