#include <iostream>
#include <random>
#include <vector>
#include <cmath>
#include <fstream>
#include <algorithm> 
using namespace std;

struct Keeper {
	int iA;
	int iLambda;
};

void vfun_ReadDatas(int &iXmax, int &iN, int &iX0);
void vfun_LCG(const int &iXmax, int &iX0, const int &iN);
int ifun_SetC(int& iModule);
int ifun_Random(int iFirst, const int iLast);
bool bfun_NWD(int iA, int iB);
void vfun_RandomizeLCG(const int &iModule, const int &iA, const int &iIncrease, const int &iX0, const int &iN);
void vfun_SaveToFile(const string sName, int iValue);


// W tych zmieniac z vetora na tablice
int SetMultiplier(int& iModuloValue, const std::vector<int>& factories);
void FillTabWithMultiplier(std::vector<Keeper>& TabWithMultiplier, int & iModuloValue);
void Factories(int iModuloValue, std::vector<int>& factories);
void FindMaxLambda(const std::vector <Keeper> & tabWithMultiplier, std::vector<int>& iMultiplier);
bool CheckWithTheory(int & iMultiplier, const std::vector<int>& factories, int iModuloValue);


int main() {
	int iXmax, iN, iX0;
	vfun_ReadDatas(iXmax, iN, iX0);
	vfun_LCG(iXmax, iX0, iN);

	return 0;
}


/**
* Funckja pobierająca dane do generatora
* @param iXmax xmax 
* @param iN liczba wyrazów
* @param iX0 ziarno
*/
void vfun_ReadDatas(int &iXmax, int &iN, int &iX0)	{
	cin >> iXmax >> iN >> iX0;

	while (iN < 0 || iXmax < 0 || iX0 < 0 || iX0 >= iXmax) {
		cout << "!" << endl;
		cin >> iXmax >> iN >> iX0;
	}
}

/**
* Generator losujący metodą liniową
* @param iXmax xmax
* @param iX0 ziarno
* @param iN liczba wyrazów
*/
void vfun_LCG(const int &iXmax, int &iX0, const int &iN) {
	int iModule = iXmax + 1;
	int iC = ifun_SetC(iModule);
	
	
	vector<int> factories;

	Factories(iModule, factories);

	int iMultiplier = SetMultiplier(iModule, factories);

	vfun_RandomizeLCG(iModule, iMultiplier, iC, iX0, iN);
}

/**
* Wyznaczanie przyrostu c
* @param iModule moduł m
* @return wartosc przyrostu c
*/
int ifun_SetC(int& iModule) {
	int iIncrease = ifun_Random(1, iModule);

	while (bfun_NWD(iModule, iIncrease)) {
		iIncrease = ifun_Random(1, iModule);
	}

	return iIncrease;
}

/**
* Losowanie liczby
* @param iFirst wyraz od ktorego losujemy
* @param iLast wyraz do ktorego losujemy
* @return dist(rd) wylosowana liczba
*/
int ifun_Random(int iFirst, const int iLast) {
	random_device rd;
	uniform_int_distribution<int>dist(iFirst, iLast - 1);
	return dist(rd);
}

/**
* Najwiekszy wspolny dzielnik
* @param iA liczba pierwsza
* @param iB liczba druga
* @return false gdy NWD=1
* @return true gdy NWD!=1
*/
bool bfun_NWD(int iA, int iB) {
	do {
		if (iA > iB) {
			iA = iA - iB;
		}
		else {
			iB = iB - iA;
		}
	} while (iA != iB);

	if (iA == 1) {
		return false;
	}
	else {
		return true;
	}
}

/**
* Zapisywanie do pliku
* @param sName nazwa pliku
* @param iValue wartość x ze wzoru
*/
void vfun_SaveToFile(const string sName, int iValue) {
	ofstream fsFile;
	fsFile.open(sName, ios::app);
	fsFile << iValue << endl;
	fsFile.close();
}

/**
* Podstawienie wartości do wzoru głównego
* iModule moduł m
* iA mnożnik a
* iIncrease przyrost c
* iX0 ziarno x0
* iN liczba wyrazów
*/
void vfun_RandomizeLCG(const int &iModule, const int &iA, const int &iIncrease, const int &iX0, const int &iN) {
	int x = iX0;

	for (int i = 0; i < iN; i++) {
		x = (iA * x + iIncrease) % iModule;
		vfun_SaveToFile("Wyniki.txt", x);
	}
}

// Odtad musze pozmieniac

int SetMultiplier(int& iModuloValue, const std::vector<int>& factories)
{
	int iMultiplier;

	std::vector<Keeper> TabWithMultiplier;
	FillTabWithMultiplier(TabWithMultiplier, iModuloValue);

	std::vector<int> Multiplier;
	FindMaxLambda(TabWithMultiplier, Multiplier);
	for (int i = 0; i < Multiplier.size(); ++i)
	{
		if (CheckWithTheory(Multiplier[i], factories, iModuloValue))
			return Multiplier[i];
	}
	int MaxMultiplier = Multiplier[0];
	for (int i = 1; i < Multiplier.size(); ++i)
	{
		if (MaxMultiplier < Multiplier[i])
		{
			MaxMultiplier = Multiplier[i];
		}
	}
	return MaxMultiplier;
}

void FillTabWithMultiplier(std::vector<Keeper>& TabWithMultiplier, int& iModuloValue)
{
	int podstawa = 2;
	int lambda = 1;
	long long temp = podstawa;
	int i = 0;
	Keeper temporaryKeeper;

	while (podstawa < iModuloValue)
	{
		while (NWD(iModuloValue, podstawa))
		{
			++podstawa;
			temp = podstawa;

		}

		while (temp % iModuloValue != 1)
		{
			lambda++;
			temp *= podstawa;
			if (lambda > 100)break;

		}

		temporaryKeeper.iA = podstawa;
		temporaryKeeper.iLambda = lambda;

		TabWithMultiplier.push_back(temporaryKeeper);

		++podstawa;
		lambda = 1;
		temp = podstawa;

	}

}

void Factories(int iModuloValue, std::vector<int>& factories)
{
	int g = sqrt(iModuloValue);

	for (int i = 2; i <= g; i++)
	{
		while (iModuloValue % i == 0)
		{
			factories.push_back(i);
			iModuloValue /= i;
		}
		if (iModuloValue != 1)
		{
			return;
		}

	}
	factories.push_back(iModuloValue);
}

void FindMaxLambda(const std::vector <Keeper> & tabWithMultiplier, std::vector<int>& iMultiplier)
{
	int iTemporaryMax = tabWithMultiplier[0].iLambda;
	for (int i = 1; i < tabWithMultiplier.size(); i++)
	{
		if (iTemporaryMax < tabWithMultiplier[i].iLambda)
		{
			iTemporaryMax = tabWithMultiplier[i].iLambda;
		}
	}
	for (int i = 0; i < tabWithMultiplier.size(); ++i)
	{
		if (iTemporaryMax == tabWithMultiplier[i].iLambda)
		{
			iMultiplier.push_back(tabWithMultiplier[i].iA);
		}
	}
}

bool CheckWithTheory(int & Multiplier, const std::vector<int>& factories, int iModuloValue)
{
	int b = Multiplier - 1;
	for (int i = 0; i < factories.size(); ++i)
	{
		if (b % factories[i] != 0)
		{
			return false;
		}
	}
	if (iModuloValue % 4 == 0)
	{
		if (b % 4 == 0)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
}