#include <iostream>
#include <cassert>
#include <cmath>

using namespace std;

class ValueError {
private:
    const char* txt;
public:
    ValueError(const char* reason = ""):
         txt(reason)
    {}
    
    const char* what() const {
        return txt;
    }
};

int gcd(int m, int n);
double fastPower(double a, int n);
int powerMod(int a, int n, int m);
void extEucl(
    int m, int n,
    int& d, int& u, int& v
);
int invMod(int x, int m);
double loga(double y, double a, double eps = 1e-8);

int main() {
    while (true) {
        int m, n;
        cout << "m, n: ";
        cin >> m >> n;
        if (!cin.good())
            break;
        int d = gcd(m, n);
        cout << "gcd(m, n) = " << d << endl;
        
        int u, v;
        extEucl(m, n, d, u, v);
        cout << d << " == " << u << "*" << m <<
             " + " << v << "*" << n << endl;
             
        cout << "Compute inverse modulo m: enter x, m> ";
        int x;
        cin >> x >> m;
        try {
            int y = invMod(x, m);
            cout << "invMod(x, m) = " << y << endl;
        } catch (const ValueError& e) {
            cout << "ValueError exception: " << e.what() << endl;
        }    
        
        double a;
        cout << "a, n: ";
        cin >> a >> n;
        double p = fastPower(a, n);
        cout << "a^n = " << p << endl;
        
        int b;
        cout << "For powerMod(b, n, m), enter b, n, m> ";
        cin >> b >> n >> m;
        x = powerMod(b, n, m);
        cout << "b^n (mod m) = " << x << endl;
        
        cout << "log_a(y): enter a, y> ";
        double y;
        cin >> a >> y;
        double xxx = loga(y, a);
        cout << "log_a(y) = " << xxx << endl;
        cout << "standard log(y)/log(a) = " <<
            log(y)/log(a) << endl; 
   }
   return 0;
}

int gcd(int m, int n) {
    int a = m; int b = n;
    // assert: gcd(a, b) == gcd(m, n)
    while (b != 0) {
        // (a, b) -> (b, r) => number of steps = O(log_2(n))
        int r = a%b;
        a = b; b = r;
    }
    // assert: gcd(a, b) == gcd(m, n) && b == 0
    if (a > 0)
        return a;
    else
        return (-a);
}

double fastPower(double a, int n) {
    double p = 1.;
    double b = a;
    int k = n;
    // assert: p * b^k == a^n
    while (k > 0) {
        if (k%2 == 0) {
            k /= 2; b *= b;
        } else {
            k -= 1; p *= b;
        }
    }
    return p;
}
   
int powerMod(int a, int n, int m) {
    int p = 1;
    int b = a;
    int k = n;
    // assert: p * b^k == a^n
    while (k > 0) {
        if (k%2 == 0) {
            k /= 2; b = (b*b)%m;
        } else {
            k -= 1; p = (p*b)%m;
        }
    }
    return p;
}

void extEucl(
    int m, int n,
    int& d, int& u, int& v
) {
    int a = m; int b = n;
    int u1 = 1; int v1 = 0;
    int u2 = 0; int v2 = 1;
    assert(a == u1*m + v1*n);
    assert(b == u2*m + v2*n);
    // assert(gcd(a, b) == gcd(m, n));
    while (b != 0) {
        int q = a/b; int r = a%b;
        a = b; b = r;
        int tmp = u1; u1 = u2;
        u2 = tmp - q*u2; 
        tmp = v1; v1 = v2;
        v2 = tmp - q*v2;
    }
    assert(a == u1*m + v1*n);
    assert(b == u2*m + v2*n);
    assert(b == 0);
        
    if (a > 0) {
        d = a; u = u1; v = v1;
    } else {
        d = (-a); u = (-u1); v = (-v1);
    }
}

int invMod(int x, int m) {
    int d, u, v;
    extEucl(x, m, d, u, v);
    assert(d == u*x + v*m);
    if (d != 1)
        throw ValueError("invMod: x is not invertible");
    return u;
}

double loga(double y, double a, double eps /* = 1e-8 */) {
    double x = 0.;
    double z = y;
    double t = 1.;
    // assert: a^x * z^t == y
    while (z < 1./a || z > a || fabs(t) > eps) {
        if (z < 1./a) {
            z *= a;
            x -= t;
        } else if (z > a) {
            z /= a;
            x += t;
        } else {
            z *= z;
            t /= 2.;
        }
    }
    return x;
}