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