Euler's Criterion

Your friend gives you an equation  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.

Example:

Input:  a = 4, m = 7
Output: YES

Approach

Java

public class EulerCriterion {
    public static void main(String[] args) {

        int a = 4;
        int m = 7;

        System.out.println(solve(a, m));

    }

    static long power(long a, long b, long m) {
        long ans = 1;
        a = a % m;
        while (b > 0) {
            if (b % 2 == 1)
                ans = (ans * a) % m;

            a = (a * a) % m;
            b = b >> 1;
        }
        return (ans % m);
    }

    static String solve(int a, int m) {

        if (a == 0)
            return "YES";
        if (power(a, (m - 1) / 2, m) == 1)
            return "YES";

        return "NO";
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

long long power(long long a, long long b,
                long long m)
{
    long long ans = 1;
    a = a % m;
    while (b)
    {
        if (b & 1)
            ans = (ans * a) % m;

        a = (a * a) % m;
        b = b >> 1;
    }
    return (ans % m);
}
string solve(int a, int m)
{

    if (a == 0)
        return "YES";
    if (power(a, (m - 1) / 2, m) == 1)
        return "YES";

    return "NO";
}

int main()
{

    int a = 4;
    int m = 7;

    cout << solve(a, m) << "\n";

    return 0;
}