#include <iostream>
#include <random>
#define ll long long
using namespace std;


int *dynamic_board(int m, int &Size)
{
	int *t = nullptr;


	int k = 2; //ustawiamy k na pierwsza liczbe pierwsza
	while (m > 1) //rozbijamy m
	{
		while (m % k == 0) // dopoki liczba jest podzielna przez k
		{

			m /= k;
			Size++;

		}
		k++;

	}
	try
	{
		t = new int(Size);
	}
	catch (bad_alloc) //badam poprawnosc alokacji
	{
		exit(0);
	}
	return t;

}

void losuj(int &los, int m)//funkcja do losowania ziarna i c
{
	random_device rd;
	mt19937 mt(rd());
	uniform_int_distribution<int>dist(0, m - 1);
	los = dist(mt);
}

void wpisz_do_tab(int *tab, int m) //do wpisnia do tablicy rozkladu liczby m
{
	int i = 0, k = 2;
	while (m > 1) //rozbijamy m
	{
		while (m % k == 0) // dopoki liczba jest podzielna przez k
		{

			m /= k;
			tab[i] = k;
			i++;
		}
		k++;
	}
}

int NWD(int a, int b)
{
	while (a != b)
		if (a>b)
			a -= b; //lub a = a - b;
		else
			b -= a; //lub b = b-a
	return a; // lub b - obie zmienne przechowują wynik NWD(a,b)
}
ll modular_pow(ll podstawa, ll wykladnik, int modulo);

int *znajdz_lambde(int m, int *t2)
{
	int lambda;
	int wynik;
	int pomocniczy_indeks = 0;
	for (int a = 2; a < m; a++)
	{
		lambda = 1;
		do {
			wynik = modular_pow(a, lambda, m);
			lambda++;
			} while (wynik != 1 && lambda<m);
			t2[pomocniczy_indeks++] = a;
			t2[pomocniczy_indeks++] = --lambda;
			cout << "A to " << a << " lambda to " << lambda << endl;

	}
	return t2;
}

ll modular_pow(ll podstawa, ll wykladnik, int modulo) // funkcja do wyliczenia wielkich poteg
{
	ll wynik = 1;
	while (wykladnik > 0)
	{
		if (wykladnik % 2 == 1)
			wynik = (wynik * podstawa) % modulo;
		wykladnik = wykladnik >> 1;
		podstawa = (podstawa * podstawa) % modulo;
	}
	return wynik;
}
int *dynamic_board2(int Size)
{
	int *t2 = nullptr;
	try
	{
		t2 = new int(Size);
	}
	catch (bad_alloc) //badam poprawnosc alokacji
	{
		exit(0);
	}
	return t2;
}
void max_lambda(int *t2, int m)
{
	int maksimum=t2[1];
	for (int a = 1; a < m; a +=2)
	{
		if (t2[a] >= maksimum)
		{
			maksimum = t2[a];
			cout << "Max lambda to " << maksimum << " dla a= " << a << endl;
		}
	}
}

/*void max_lambda(int *t2, int m)  //pisane samemu nr1, zle
{
	int lambda = 0;
	int a = 0, b=0;
	for (int i = 1; i < m; i += 2)
	{
		if (t2[i] > lambda)
		{
			lambda = t2[i];
			a = i;

			//	}
			cout << "Max lambda to " << --lambda << "a a to " << a << endl;
		}
		else if (t2[i] == lambda)
		{
			b = i;
			cout << "Z 2 warunku max lambda " << lambda << "a to " << b;
		}
	}

}*/
int main()
{

	int Size = 0;
	int *t=nullptr;
	int *t2 = nullptr;
	int x_zero; // ziarno
	cout << "Wybierz metode, ktora chcesz wygenerowac liczbe" << endl;
	cout << "1.Liniowa metoda kongruencyjna" << endl;
	cout << "2.Addytywna metoda kongruencyjna" << endl;
	int wybor;
	cin >> wybor;
	switch (wybor)
	{
	case 1: cout << "Wybrales nr 1" << endl;
		int x_max, n; //zakres liczb pseudolosowych, ilosc wylosowanych liczb

		cout << "Podaj ile chcesz wylosowac liczb" << endl;
		cin >> n;
		cout << "Podaj zakres liczb psuedolosowych" << endl;
		cin >> x_max;

		int m;
		m = x_max + 1;
		t = dynamic_board(m, Size);
		losuj(x_zero, m);
		cout << "Wylosowane ziarno to " << x_zero << endl;
		int c;

		do
		{
			losuj(c, m);
		} while (NWD(c,m) != 1);

		wpisz_do_tab(t, m);
		losuj(c, m);
		cout << "Wylosowany przyrost c to " << c << endl;
		cout <<"NWD x_zero i c to "<< NWD(x_zero, c)<<endl;
		t2 = dynamic_board2(2*m - 4); //2*(m-2)
		znajdz_lambde(m, t2);
		max_lambda(t2, m);
		break;
	case 2: cout << "Wybrales nr 2" << endl; break;
	default: cout << "Zly wybor" << endl; break;
	}
	system("pause");
	return 0;
}