// ConsoleApplication47.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <fstream>
#include <math.h>

using namespace std;

//int n = 10000;

const int N = 10000;
unsigned int gist[10];

//wrong
/*void swap(int a, int b) {
    int t = a;
    a = b;
    b = t;
}
*/
void swap1(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

void swap2(int& a, int& b) {
    int t = a;
    a = b;
    b = t;
}

int gnsd(int a, int b, int& x, int& y) {
    int u1 = 1, u2 = 0, u3 = a, v1 = 0, v2 = 1, v3 = b;
    while (v3 != 0) {
        int q = u3 / v3;
        //t=u-vq
        int t1 = u1 - v1 * q;
        int t2 = u2 - v2 * q;
        int t3 = u3 - v3 * q;
        //u=v;
        u1 = v1; u2 = v2; u3 = v3;
        //v=t;
        v1 = t1; v2 = t2; v3 = t3;
    }
    x = u1; y = u2;
    return u3;
}

//x = a^(-1) mod m - ?
int inverse(int a, int m) {
    int r;
    for (r = 1; r < m; r++)
        if ((r * a) % m == 1)
            return r;
    return 0;
}

int inverse2(int a, int m) {
    int x=1, y=0, d;
    d = gnsd(a, m, x, y);
    if (d != 1) return 0;//not exsits
    return x;
}
int powm(int a, int n, int m) {
    if (n == 1) return a % m;
    int r = powm(a, n >> 1, m);
    r = (r * r) % m;
    if ((n & 1) == 0) return r;
    return (r * a) % m;
}

int inverse3(int a, int m) {
    return powm(a, m - 2, m);
}

int pow(int a, int n) {
    if (n == 1) return a;
    int r = pow(a, n >> 1);
    r *= r;
    if ((n & 1) == 0) return r;
    return r * a;
}
int inverse_wrong(int a, int m) {
    return pow(a, m - 2) % m;
}

void main()
{
    /*
    int a = 787, c = 517, m = (1 << 11) - 1;
    unsigned int x0, x;
    double u0, u;
    x0 = 1;
    for (int i = 1; i <= N; ++i) {
        x = (a * x0 + c) % m;
        u = (double)x / m;
        gist[(int)(u*10)]++;
        x0 = x;
    }
    for (int j = 0; j < 10; j++)
        cout << j << ':' << gist[j] << endl;

    cout << endl << endl << a << " " << c << endl;
    swap2(a, c);
    cout << a << " " << c << endl << endl;
    int xx, yy;
    int d = gnsd(7, 23, xx, yy);
    cout << xx << "," << yy << endl;
    */
    
    //7^(-1) mod 23 - ?
    cout << inverse(7, 23) << endl;
    cout << inverse2(7, 23) << endl;
    cout << inverse3(7, 23) << endl;
    cout << inverse_wrong(7, 23) << endl;


}