// https://infoarena.ro/problema/inversmodular
// Se dau doua numere A si N, cu 1 ≤ A ≤ N-1, prime intre ele (cel mai mare divizor comun al lor este 1). Sa se determine X intre 1 si N-1 astfel incat A * X sa fie congruent cu 1, modulo N (restul impartirii lui A * X la N sa fie 1). Numarul X se va numi inversul modular al lui A.

#include <iostream>
#include <fstream>

using namespace std;

// Functia calculeaza coeficientii x si y astfel incat a * x + b * y = gcd(a, b) utilizand algoritmul lui Euclid extins.
void EuclidExtins(int a, int b, int& x, int& y)
{
	if (b == 0)	// cazul in care b este 0 - cazul de baza al recursivitatii
	{
		x = 1;	
		y = 0;	// a * 1 + b * 0 = a
	}
	else
	{
		int x1, y1;
		EuclidExtins(b, a % b, x1, y1);
		x = y1;
		y = x1 - (a / b) * y1;
	}
}


int main()
{
	ifstream fin("inversmodular.in");
	ofstream fout("inversmodular.out");

	if (!fin.is_open())
	{
		cerr << "Eroare la deschiderea fisierului de intrare!";
		return 1;
	}

	if (!fout.is_open())
	{
		cerr << "Eroare la deschiderea fisierului de iesire!";
		return 1;
	}


	int A, N;
	fin >> A >> N;
	if (!(A >= 1 && A < N && N < 2000000000))
	{
		cerr << "Nu se respecta restrictiile impuse.";
		return 1;
	}

	int x, y;	// x va fi inversul lui A modulo N, iar y va fi coeficientul pentru N in ecuatia lui Euclid extins
	EuclidExtins(A, N, x, y);

	if (x < 0)
	{
		x = N + x % N; // astfel ne asiguram ca inv este pozitiv
	}
	
	fout << x << endl;

	fin.close();
	fout.close();
	return 0;
}