#include <iostream>
#include <fstream>
#include <algorithm> 
#include <random>
#include <vector>
#include <cmath>

using namespace std;

struct alam {
	int a;
	int lambda;
};

struct Para {
	int a;
	int b;
};

void makslambda(const vector <alam> & tabmnoznikow, vector<int>& mnoznik) {
	int maks = tabmnoznikow[0].lambda;
	for (int i = 1; i < tabmnoznikow.size(); i++) {
		if (maks < tabmnoznikow[i].lambda) {
			maks = tabmnoznikow[i].lambda;
		}
	}
	for (int i = 0; i < tabmnoznikow.size(); ++i) {
		if (maks == tabmnoznikow[i].lambda) {
			mnoznik.push_back(tabmnoznikow[i].a);
		}
	}
}

vector<Para>tablica_par = {
	{ 0,1 },{ 0,2 },{ 0,3 },{ 1,4 },{ 0,5 },{ 0,6 },{ 2,6 },{ 3,8 },{ 2,9 },{ 1,10 },{ 0,14 },{ 2,16 },{ 6,17 },{ 2,19 },{ 1,20 },{ 0,21 },{ 4,22 },{ 2,24 },{ 2,27 },
	{ 1,28 },{ 2,30 },{ 12,32 },{ 1,34 },{ 10,35 },{ 3,38 },{ 2,40 },{ 4,46 },{ 8,49 },{ 2,51 },{ 24,54 },{ 6,56 },{ 18,57 },{ 0,59 },{ 0,62 },{ 17,64 },{ 8,67 },
	{ 5,70 },{ 24,72 },{ 8,78 },{ 3,80 },{ 12,83 },{ 12,86 },{ 37,88 },{ 1,92 },{ 20,93 },{ 10,94 },{ 5,96 },{ 10,98 }
};

void czytajdane(int & max, int & liczlosowe, int & Seed) {
	cin >> max >> liczlosowe >> Seed;
	while (liczlosowe < 0 || max < 0 ||
		Seed < 0 || Seed >= max) {
		cout << "!" << endl;
		cin >> max >> liczlosowe >> Seed;
	}
}

int losowanie(int pierwszy, const int modulo) {
	random_device rd;
	uniform_int_distribution<int>dist(pierwszy, modulo - 1);
	return dist(rd);
}

bool NWD(int modulo, int wzrost) {
	do {
		if (modulo > wzrost) {
			modulo = modulo - wzrost;
		}
		else {
			wzrost = wzrost - modulo;
		}
	} while (modulo != wzrost);
	if (modulo == 1) {
		return false;
	}
	else {
		return true;
	}
}

int przyrost(int& modulo) {
	int wzrost = losowanie(1, modulo);
	while (NWD(modulo, wzrost)) {
		wzrost = losowanie(1, modulo);
	}
	return wzrost;
}

bool teoria(int & mnoznik, const vector<int>& pierwsze, int modulo) {
	int b = mnoznik - 1;
	for (int i = 0; i < pierwsze.size(); ++i) {
		if (b % pierwsze[i] != 0) {
			return false;
		}
	}
	if (modulo % 4 == 0) {
		if (b % 4 == 0) {
			return true;
		}
		else {
			return false;
		}
	}
}

void wypelnij_mnoznikami(vector<alam>& tabmnoznikow, int& modulo) {
	int podstawa = 2;
	int lambda = 1;
	long long tmp = podstawa;
	int i = 0;
	alam tymczasowe_alam;
	while (podstawa < modulo) {
		while (NWD(modulo, podstawa)) {
			++podstawa;
			tmp = podstawa;
		}
		while (tmp % modulo != 1) {
			lambda++;
			tmp *= podstawa;
			if (lambda > 100)break;
		}
		tymczasowe_alam.a = podstawa;
		tymczasowe_alam.lambda = lambda;
		tabmnoznikow.push_back(tymczasowe_alam);
		++podstawa;
		lambda = 1;
		tmp = podstawa;
	}
}


int mnoz(int& modulo, const vector<int>& czemu_tak_trudno) {
	int mnoznik;
	vector<alam> tabmnoznikow;
	wypelnij_mnoznikami(tabmnoznikow, modulo);
	vector<int> vecmnoznik;
	makslambda(tabmnoznikow, vecmnoznik);
	for (int i = 0; i < vecmnoznik.size(); ++i) {
		if (teoria(vecmnoznik[i], czemu_tak_trudno, modulo)) {
			return vecmnoznik[i];
		}
	}
	int maxmnoznik = vecmnoznik[0];
	for (int i = 1; i < vecmnoznik.size(); ++i) {
		if (maxmnoznik < vecmnoznik[i]) {
			maxmnoznik = vecmnoznik[i];
		}
	}
	return maxmnoznik;
}

void napierwsze(int modulo, vector<int>& pierwsze) {
	int x = sqrt(modulo);
	for (int i = 2; i <= x; i++) {
		while (modulo % i == 0) {
			pierwsze.push_back(i);
			modulo /= i;
		}
		if (modulo != 1) {
			return;
		}
	}
	pierwsze.push_back(modulo);
}

void zapis(const string nazwa, int wartosc) {
	ofstream wyj;
	wyj.open(nazwa, ios::app);
	wyj << wartosc << endl;
	wyj.close();
}

void losoweLCG(const int & modulo, const int & mnoznik, const int & przyrost, const int & seed, const int & liczlosowe) {
	int x = seed;
	for (int i = 0; i < liczlosowe; ++i) {
		x = (mnoznik * x + przyrost) % modulo;
		zapis("Wyniki.txt", x);
	}
}

void LCG(const int & maksymalne, int & seed, const int & liczlosowe) {
	int modulo = maksymalne + 1;
	int rosnie = przyrost(modulo);
	vector<int> pierwsze;
	napierwsze(modulo, pierwsze);
	int mnoznik = mnoz(modulo, pierwsze);
	losoweLCG(modulo, mnoznik, rosnie, seed, liczlosowe);
}

void czytajdane(int& rozmiar, int& wartosc) {
	cin >> rozmiar >> wartosc;
	while (rozmiar < 0 || wartosc < 0) {
		cout << "!";
		cin >> rozmiar >> wartosc;
	}
}

Para znajdzpary(int rozmiar) {
	Para idealna = tablica_par[0];
	int i = 0;
	if (rozmiar > 97)return tablica_par[47];
	while (tablica_par[i].b < rozmiar) {
		if (tablica_par[i].b < rozmiar) {
			idealna = tablica_par[i];
		}
		i++;
	}
	return idealna;
}

void odczyt(string nazwa, int rozmiar, vector<int>& tab) {
	ifstream plik;
	plik.open(nazwa.c_str());
	int tmp;
	if (!plik) {
		cout << "!";
		exit(EXIT_FAILURE);
	}
	for (int i = 0; i < rozmiar; ++i) {
		plik >> tmp;
		tab.push_back(tmp);
	}
	plik.close();
}

void Generuj(const Para& idealnapara, const int & modulo, const int& rozmiar, vector<int>& tab) {
	int k = idealnapara.a;
	int j = idealnapara.b;
	for (int i = 0; i <= 200 * rozmiar; ++i) {
		tab[k] = (tab[j] + tab[k]) % modulo;
		if (k == 0) {
			k = rozmiar;
		}
		else if (j == 0) {
			j = rozmiar;
		}
		--j;
		--k;
	}
	for (int i = 0; i < rozmiar; ++i) {
		zapis("wyniki2.txt", tab[i]);
	}
}

void ijeszczeadytywnie(const int & modul, const int & rozmiar) {
	vector<int> tab;
	Para idealnapara = znajdzpary(rozmiar);
	odczyt("Wyniki.txt", rozmiar, tab);
	reverse(tab.begin(), tab.end());
	Generuj(idealnapara, modul, rozmiar, tab);
}

void czysc(const string& nazwa) {
	ofstream wyj;
	wyj.open(nazwa);
	wyj.close();
}

int main()
{
	int maksymalna, liczlosowe, seed, rozmiar, modulo, wybor;
	czysc("Wyniki.txt");
	czysc("wyniki2.txt");
	cout << "Liniowo - 1 " << endl;
	cout << "Adytywnie - 2" << endl;
	cin >> wybor;
	if (wybor == 1) {
		czytajdane(maksymalna, liczlosowe, seed);
		LCG(maksymalna, seed, liczlosowe);
	}
	else if (wybor == 2) {
		czytajdane(rozmiar, modulo);
		seed = losowanie(0, rozmiar);
		LCG(modulo, seed, rozmiar);
		ijeszczeadytywnie(modulo, rozmiar);
	}
	else {
		cout << "!";
	}
	return 0;
}