#include <stdio.h>

// Functie ajutatoare
// Indicatorul lui Euler
int indEuler(int n) {
  int euler, d;

  euler = n;
  d = 2;
  while (d * d <= n) {
    if (n % d == 0) {
      euler = euler / d * (d - 1);

      while (n % d == 0)
        n /= d;
    }

    ++d;
  }

  if (n > 1)
    euler = euler / n * (n - 1);

  return euler;
}

// Functie ajutatoare
// Ridicare la putere in timp logaritmic
int lgput(int a, int n, int mod) {
  int p;

  p = 1;
  while (n > 0) {
    if (n % 2 == 1)
        p = (long long)p * a % mod;
    a = (long long)a * a % mod;
    n = n / 2;
  }

  return p;
}

// Functie ajutatoare
// Euclid extins
void euclid(int a, int b, int *d, int *x, int *y) {
  if (b == 0) {
    *d = a;
    *x = 1;
    *y = 0;
  } else {
    int x0, y0;
    euclid(b, a % b, d, &x0, &y0);
    *x = y0;
    *y = x0 - (a / b) * y0;
  }
}

// Varianta #1
int invMod1(int a, int m) {
  int inv;

  inv = 1;
  while (inv < m && a * inv % m != 1)
    ++inv;

  return inv;
}

// Varianta #2 Cazul 1 (m e prim)
int invMod21(int a, int m) {
  return lgput(a, m - 2, m);
}

// Varianta #2 Cazul 2 (m nu e prim)
int invMod22(int a, int m) {
  return lgput(a, indEuler(m) - 1, m);
}

// Varianta #3
int invMod3(int a, int m) {
  int d, x, y;

  // a * x + m * y = cmmdc(a, m)
  // cmmdc(a, m) = 1
  // => a * x + m * y = 1
  // => a * x % m = 1
  euclid(a, m, &d, &x, &y);
  return x;
}

int main() {
  int a = 6, m = 9999991;

  printf("---------Varianta 1: %d\n", invMod1(a, m));
  printf("Varianta 2, Cazul 1: %d\n", invMod21(a, m));
  printf("Varianta 2, Cazul 2: %d\n", invMod22(a, m));
  printf("---------Varianta 3: %d\n", invMod3(a, m));

  return 0;
}