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

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);
int *ifun_MakeTab(const int iSize);



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;
	}
}

/**
* Zbieranie danych do generatora 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 *iPrimeNumbersTab) {
	int iModule = iXmax + 1;
	int iC = ifun_SetC(iModule);
	ifun_PrimeNumbers(iModule);
	int iMultiplier = ifun_SetA(iModule, iPrimeNumbersTab);
	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);
	}
}

/**
* Proba tworzenia tablicy
* @param iSize rozmiar
* @return iTab tablica jeśli udało się stworzyć
*/
int *ifun_MakeTab(const int iSize) {
	int *iTab;

	try {
		iTab = new int[iSize];
	}
	catch (bad_alloc &bad) {
		cout << "!";
		exit(EXIT_FAILURE);
	}

	return iTab;
}

/**
* Zlicza czynniki pierwsze liczby
* @param iValue liczba sprawdzana
* @return iCont liczba pierwszych
*/
int ifun_CountPrime(int iValue) {
	int iK = 2, iCount = 0;
	
	while (iValue>1) {
		while (iValue%iK == 0){
			iCount++;
			iValue /= iK;
		}
		iK++;
	}
	
	return iCount;
}

/**
* Wypelnia tablice dzielnikami pierwszymi liczby
* @param iValue liczba
* @return iPrimeNumbersTab wypelniona tablica
*/
int *ifun_PrimeNumbers(int iValue) {
	int iSize = ifun_CountPrime(iValue);
	int *iPrimeNumbersTab = ifun_MakeTab(iSize);
	int g = sqrt(iValue);

	for (int i = 2, j=0; i <= g; i++) {
		while (iValue % i == 0)
		{
			iPrimeNumbersTab[j] = i;
			iValue /= i;
			j++;
		}
	}
	return iPrimeNumbersTab;
}

/**
* Sprawdza z teorią
* @param iA podstawa do potegowania
* @param iPrimeNumbersTab tablica dzielnikow ktore sa pierwsze
* @param iValue moduł m
* @return true zgodne ze wszystkim
* @return false jesli sie nie zgadza
*/
bool bfun_CheckWithTheory(int iA, int *iPrimeNumbersTab, int iModule)
{
	int b = iA - 1;
	int iSize = ifun_CountPrime(iModule);
	for (int i = 0; i < iSize; i++)
	{
		if (b % iPrimeNumbersTab[i] != 0)
		{
			return false;
		}
	}
	if (iModule % 4 == 0)
	{
		if (b % 4 == 0)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
}

int ifun_SetA(int iModule, int *iPrimeNumbersTab) {
	int iA, iLambda, iMaksLambda = 0, iCount = 0;
	int *iTabA = ifun_MakeTab(100);	
	
	for (int i = 0; i < 100; i++) {
		iTabA[i] = 0;
	}

	for (iA = 2, iLambda = 1; iA < iModule; iA++, iLambda++) {
		int iPowAandLambda = pow(iA, iLambda);
	
		while (bfun_NWD(iA, iModule) == false) {	
			while (iPowAandLambda % iModule == 1) {	
				if (iLambda > iMaksLambda) {		
					for (int i = 0; i < 100; i++) {
						iTabA[i] = 0;
					}

					iCount = 1;					
					iMaksLambda = iLambda;
					iTabA[iCount] = iA;
				}
				if (iLambda == iMaksLambda) {
					iCount++;
					iTabA[iCount] = iA;
				}
			}
		}
	}

	for (int i = 0; i < iCount; i++) {
		if (bfun_CheckWithTheory(iA, iPrimeNumbersTab, iModule) == true) {
			iA = iTabA[i];
		}
		else {
			iA = iTabA[iCount];
		}
	}
}