#include <cassert>
#include "Zm.h"

int gcd(int m, int n) {
    int a = m;
    int b = n;
    // (a, b) -> (b, r), where r is a reminder of dividing a by b
    // Invariant: gcd(a, b) = gcd(b, r)
    //     a = q*b + r,  |r| < |b|  =>
    // sets of common divizors for pairs (a, b) and (b, r) are equal
    while (b != 0) {
        int r = a%b;
        a = b; b = r;
    }
    assert(b == 0);
    // gcd(a, 0) = a
    return a;
}

// Extended Euclid's Algorithm
// Input: integer numbers m, n, one of them must be nonzero.
// Output: d = gcd(m, n) and integers u, v such that
//     d = u*m + v*n
void extEucl(
    int m, int n,
    int& d, int& u, int& v
) {
    // Invariant:
    //     gcd(a, b) = gcd(m, n),
    //     a = u1*m + v1*n,
    //     b = u2*m + v2*n
    int a = m, b = n;
    int u1 = 1, v1 = 0;
    int u2 = 0, v2 = 1;
    // assert(gcd(a, b) = gcd(m, n));
    assert(a == u1*m + v1*n && b == u2*m + v2*n);
    while (b != 0) {
        assert(a == u1*m + v1*n && b == u2*m + v2*n);
        int q = a/b; int r = a%b;
        assert(a == q*b + r);
        a = b; b = r;
        // (a, b) <-- (b, r)
        // u1' = u2; v1' = v2
        // r = a - q*b = (u1*m + v1*n) - q*(u2*m + v2*n) =
        //   = (u1 - q*u2)*m + (v1 - q*v2)*n
        // u2' = u1 - q*u2; v2' = v1 - q*v2;
        int tmp = u1; u1 = u2;
        u2 = tmp - q*u2;
        tmp = v1; v1 = v2;
        v2 = tmp - q*v2;
    }
    assert(b == 0);
    assert(a == u1*m + v1*n && b == u2*m + v2*n);
    if (a >= 0) {
        d = a;
        u = u1; v = v1;
    } else {
        d = (-a);
        u = (-u1); v = (-v1);
    }
}

int powermod(int a, int n, int m) {
    assert(n >= 0 && m != 0);
    //     b^k * p == a^n (mod m)
    // End of loop condition: k == 0
    int b = a; int k = n; int p = 1;
    while (k > 0) {
        if (k%2 == 0) {
            k /= 2; b = (b*b)%m;
        } else {
            k -= 1;
            p = (p*b)%m;
        }
    }
    return p;
}
        
// Using exceptions for error processing
// throw MyException("Reason of error");
//
// try {
//     // Dangerous code
//     . . . 
// } catch (MyException& e) {
//     // Processing exception
//     cerr << "Exception: " << e.what() << endl;
// } catch (SomeOtherException& e) {
//     // Processing another exception
//     . . .
// }

int Zm::m = 7;  // Definition of static variable of class Zm