#include <iostream>
#include <random>
#include <vector>
#include <cmath>
#include <fstream>
#include <algorithm>
using namespace std;
struct Keeper {
int iA;
int iLambda;
};
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);
// W tych zmieniac z vetora na tablice
int SetMultiplier(int& iModuloValue, const std::vector<int>& factories);
void FillTabWithMultiplier(std::vector<Keeper>& TabWithMultiplier, int & iModuloValue);
void Factories(int iModuloValue, std::vector<int>& factories);
void FindMaxLambda(const std::vector <Keeper> & tabWithMultiplier, std::vector<int>& iMultiplier);
bool CheckWithTheory(int & iMultiplier, const std::vector<int>& factories, int iModuloValue);
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;
}
}
/**
* Generator 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 iModule = iXmax + 1;
int iC = ifun_SetC(iModule);
vector<int> factories;
Factories(iModule, factories);
int iMultiplier = SetMultiplier(iModule, factories);
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);
}
}
// Odtad musze pozmieniac
int SetMultiplier(int& iModuloValue, const std::vector<int>& factories)
{
int iMultiplier;
std::vector<Keeper> TabWithMultiplier;
FillTabWithMultiplier(TabWithMultiplier, iModuloValue);
std::vector<int> Multiplier;
FindMaxLambda(TabWithMultiplier, Multiplier);
for (int i = 0; i < Multiplier.size(); ++i)
{
if (CheckWithTheory(Multiplier[i], factories, iModuloValue))
return Multiplier[i];
}
int MaxMultiplier = Multiplier[0];
for (int i = 1; i < Multiplier.size(); ++i)
{
if (MaxMultiplier < Multiplier[i])
{
MaxMultiplier = Multiplier[i];
}
}
return MaxMultiplier;
}
void FillTabWithMultiplier(std::vector<Keeper>& TabWithMultiplier, int& iModuloValue)
{
int podstawa = 2;
int lambda = 1;
long long temp = podstawa;
int i = 0;
Keeper temporaryKeeper;
while (podstawa < iModuloValue)
{
while (NWD(iModuloValue, podstawa))
{
++podstawa;
temp = podstawa;
}
while (temp % iModuloValue != 1)
{
lambda++;
temp *= podstawa;
if (lambda > 100)break;
}
temporaryKeeper.iA = podstawa;
temporaryKeeper.iLambda = lambda;
TabWithMultiplier.push_back(temporaryKeeper);
++podstawa;
lambda = 1;
temp = podstawa;
}
}
void Factories(int iModuloValue, std::vector<int>& factories)
{
int g = sqrt(iModuloValue);
for (int i = 2; i <= g; i++)
{
while (iModuloValue % i == 0)
{
factories.push_back(i);
iModuloValue /= i;
}
if (iModuloValue != 1)
{
return;
}
}
factories.push_back(iModuloValue);
}
void FindMaxLambda(const std::vector <Keeper> & tabWithMultiplier, std::vector<int>& iMultiplier)
{
int iTemporaryMax = tabWithMultiplier[0].iLambda;
for (int i = 1; i < tabWithMultiplier.size(); i++)
{
if (iTemporaryMax < tabWithMultiplier[i].iLambda)
{
iTemporaryMax = tabWithMultiplier[i].iLambda;
}
}
for (int i = 0; i < tabWithMultiplier.size(); ++i)
{
if (iTemporaryMax == tabWithMultiplier[i].iLambda)
{
iMultiplier.push_back(tabWithMultiplier[i].iA);
}
}
}
bool CheckWithTheory(int & Multiplier, const std::vector<int>& factories, int iModuloValue)
{
int b = Multiplier - 1;
for (int i = 0; i < factories.size(); ++i)
{
if (b % factories[i] != 0)
{
return false;
}
}
if (iModuloValue % 4 == 0)
{
if (b % 4 == 0)
{
return true;
}
else
{
return false;
}
}
}
