HackerRank Number Theory – Euler’s Criterion

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

Cerinta

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 \leq 10^5$  
+ $2 \leq M < 10^9$, $M$ is prime  
+ $0 \leq A < M$

Cod sursa

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