#include <iostream>
#include <random>
#include <vector>
#include <string>
#include <fstream>

using namespace std;

int NWD(int a, int b) //algorytm Euklidesa
{
	while (a != b)
		if (a>b)
			a -= b;
		else
			b -= a;
	return a;
}

long int powmod(int a, int b, int m) {
	int i;
	int result = 1;
	long int x = a%m;
	for (i = 1; i <= b; i <<= 1) {
		x %= m;
		if ((b&i) != 0) {
			result *= x;
			result %= m;
		}
		x *= x;
	}
	return result;
}

vector<int> dzielnikiPierwsze(int n)
{
	vector<int> myvector;
	int k = 2; //ustawiamy k na pierwszą liczbę pierwszą
			   //rozkład liczby na czynniki pierwsze
	while (n>1)
	{
		while (n%k == 0) //dopóki liczba jest podzielna przez k
		{
			if(myvector.empty()==true || myvector.back()!=k)myvector.push_back(k);
			n /= k;
		}
		++k;
	}
	return myvector;
}

void checkN(int n) {
	if (n < 0) {
		cout << "Zmienna n posiada niepoprawna wartosc." << endl;
		getchar();
		cin.ignore();
		exit(0);
	}
}

void checkM(int n) {
	if (n <= 0) {
		cout << "Modul m posiada niepoprawna wartosc." << endl;
		getchar();
		cin.ignore();
		exit(0);
	}
}


int main() {
	int method;
	//POCZĄTEK MENU
	cout << "WYBIERZ RODZAJ GENERATORA" << endl;
	cout << "1 - GENERATOR KONGRUENTNY LGC" << endl;
	cout << "2 - GENERATOR ADDYTYWNY KONGRUENTNY" << endl;
	cin >> method;
	//KONIEC MENU
	if (method == 1) { //POCZĄTEK PIERWSZEGO GENERATORA

		//DEKLARACJE ZMIENNYCH
		int n, m, lam, c, xMax, seed, b, a = 0, x;
		vector<int> tabA;
		vector<int> tabLam;
		vector<int> czynnikim;
		tabLam.push_back(0);
		random_device rd;
		mt19937 mt(rd());
		ofstream file;
		string filename = "plik.txt";
		file.open(filename);
		cout << "PODAJ GRANICE GORNA" << endl;
		cin >> xMax;
		m = xMax + 1;
		checkM(m);
		cout << endl <<"PODAJ LICZBE LICZB PSEUDOLOSOWYCH" << endl;
		cin >> n;
		cout << endl;
		checkN(n);
		uniform_int_distribution<int>dist(1, m - 1); // LOSOWANE LICZBY Z PRZEDZIAŁU <1,m-1>

		do
		{
			c = dist(rd);
		} while (NWD(m, c) != 1); // c jest losowane aż będzie względnie pierwsze z m

		seed = dist(rd);

		for (int i = 2; i < m; i++) // wyznaczenie tych a, dla których lambda jest maksymalna (a^lam mod m =1) do wektora tabA
		{
			lam = 1;
			while (powmod(i, lam, m) != 1)
			{
				if (lam == m*m) {
					lam = 0;
					break;
				}
				++lam;
			}
			if (lam > tabLam.back()) {
				tabA.clear();
				tabLam.clear();
				tabA.push_back(i);
				tabLam.push_back(lam);
			}
			else if(lam == tabLam.back()){
				tabA.push_back(i);
				tabLam.push_back(lam);
			}
		}

		czynnikim = dzielnikiPierwsze(m); // w czynnikim przechowywane są dzielniki liczby m które są liczbami pierwszymi

		for (int i = 0; i < static_cast<int>(tabA.size()); i++) //sprawdzenie poprawności kolejnych wartości a z twierdzeniem
		{
			b = tabA.at(i) - 1;
			if (b % 4 == 0 && m % 4 == 0) {
				for (int j = 0; j < static_cast<int>(czynnikim.size()); j++)
				{
					if (czynnikim.at(j) % b == 0) {
						a = tabA.at(i);
					}
				}
			}
		}

		if (a == 0)a = tabA.back();

		x = ((a*seed) + c) % m; // pierwszą liczbę pseudolosową należy wygenerować z użyciem seeda
		file << x << endl;
		for (int i = 0; i < n-1; i++)
		{
			x = ((a*x) + c) % m; // kolejne na podstawie poprzedniej liczby pseudolosowej
			file << x << endl;
		}
		cout << "Wygenerowano plik o nazwie: " << filename << endl;
		file.close();

	} // KONIEC PIERWSZEGO GENERATORA
	else if (method == 2) // POCZĄTEK DRUGIEGO GENERATORA
	{
		cout << "Pan da 3 :)" << endl;
	} // KONIEC DRUGIEGO GENERATORA
	else {
		cout << "Niepoprawnie wybrano rodzaj generatora. " << endl;
	}
	cout << "Program sie zakonczyl.";
	getchar();
	cin.ignore();
	return 0;
}