order

#include <iostream>
#include <cmath>

typedef long long i64;
using namespace std;

i64 nod (i64 a, i64 b);
i64 eiler (i64 n);
i64 order (i64 x, i64 n);

int main(){
    i64 x, n;
    cout << "Input x, n: ";
    cin >> x >> n;
    cout << "Order: " << order(x, n);
}

i64 order (i64 x, i64 n){
    i64 count = eiler(n);
    i64 limit = sqrt(count);
    for ( i64 i = 1; i <= count; ++i )
        if ( count % i == 0 ){
            i64 xi = pow(x, i);
            if ( xi % n == 1 )
                return i;
        }
    i64 xi = pow(x, count);
    if ( xi % n == 1 )
        return count;
    else
        return 0;
}

i64 eiler(i64 n){
    i64 count = 0;
    for (i64 i = 0; i < n; ++i)
        if ( nod (i, n) == 1 )
            ++count;
    return count;
}

i64 nod (i64 a, i64 b){
    i64 temp;
    while ( a % b != 0 ){
        temp = a % b; a = b; b = temp;
    }
    return b;
}