#include <iostream>
#include <random>
#include <cmath>
#include <fstream>
using namespace std;
void vfun_ReadDatas(int &iXmax, int &iN, int &iX0);
void vfun_LCG(const int &iXmax, int &iX0, const int &iN, int *iPrimeNumbersTab);
int ifun_SetC(int &iModule);
int ifun_Random(int iFirst, const int iLast);
bool bfun_NWD(int iA, int iB);
void vfun_SaveToFile(const string sName, int iValue);
void vfun_RandomizeLCG(const int &iModule, const int &iA, const int &iIncrease, const int &iX0, const int &iN);
int *ifun_MakeTab(const int iSize);
int ifun_CountPrime(int iValue);
int *ifun_PrimeNumbers(int iValue);
bool bfun_CheckWithTheory(int iA, int *iPrimeNumbersTab, int iModule);
int ifun_SetA(int iModule, int *iPrimeNumbersTab);
int main() {
int iXmax, iN, iX0;
vfun_ReadDatas(iXmax, iN, iX0);
vfun_LCG(iXmax, iX0, iN, iPrimeNumbersTab);
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;
}
}
/**
* Zbieranie danych do generatora 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 *iPrimeNumbersTab) {
int iModule = iXmax + 1;
int iC = ifun_SetC(iModule);
ifun_PrimeNumbers(iModule);
int iMultiplier = ifun_SetA(iModule, iPrimeNumbersTab);
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);
}
}
/**
* Proba tworzenia tablicy
* @param iSize rozmiar
* @return iTab tablica jeśli udało się stworzyć
*/
int *ifun_MakeTab(const int iSize) {
int *iTab;
try {
iTab = new int[iSize];
}
catch (bad_alloc &bad) {
cout << "!";
exit(EXIT_FAILURE);
}
return iTab;
}
/**
* Zlicza czynniki pierwsze liczby
* @param iValue liczba sprawdzana
* @return iCont liczba pierwszych
*/
int ifun_CountPrime(int iValue) {
int iK = 2, iCount = 0;
while (iValue>1) {
while (iValue%iK == 0){
iCount++;
iValue /= iK;
}
iK++;
}
return iCount;
}
/**
* Wypelnia tablice dzielnikami pierwszymi liczby
* @param iValue liczba
* @return iPrimeNumbersTab wypelniona tablica
*/
int *ifun_PrimeNumbers(int iValue) {
int iSize = ifun_CountPrime(iValue);
int *iPrimeNumbersTab = ifun_MakeTab(iSize);
int g = sqrt(iValue);
for (int i = 2, j=0; i <= g; i++) {
while (iValue % i == 0)
{
iPrimeNumbersTab[j] = i;
iValue /= i;
j++;
}
}
return iPrimeNumbersTab;
}
/**
* Sprawdza z teorią
* @param iA podstawa do potegowania
* @param iPrimeNumbersTab tablica dzielnikow ktore sa pierwsze
* @param iValue moduł m
* @return true zgodne ze wszystkim
* @return false jesli sie nie zgadza
*/
bool bfun_CheckWithTheory(int iA, int *iPrimeNumbersTab, int iModule)
{
int b = iA - 1;
int iSize = ifun_CountPrime(iModule);
for (int i = 0; i < iSize; i++)
{
if (b % iPrimeNumbersTab[i] != 0)
{
return false;
}
}
if (iModule % 4 == 0)
{
if (b % 4 == 0)
{
return true;
}
else
{
return false;
}
}
}
/*
* Szuka a do wzoru glownego
* @param iModule wartosc m
* @param iPrimeNumbersTab tablica zeby sprawdzic z teorią
* @return iA znalezione a
*/
int ifun_SetA(int iModule, int *iPrimeNumbersTab) {
int iA, iLambda, iMaksLambda = 0, iCount = 0;
int *iTabA = ifun_MakeTab(100);
for (int i = 0; i < 100; i++) {
iTabA[i] = 0;
}
for (iA = 2, iLambda = 1; iA < iModule; iA++, iLambda++) {
int iPowAandLambda = pow(iA, iLambda);
while (bfun_NWD(iA, iModule) == false) {
while (iPowAandLambda % iModule == 1) {
if (iLambda > iMaksLambda) {
for (int i = 0; i < 100; i++) {
iTabA[i] = 0;
}
iCount = 1;
iMaksLambda = iLambda;
iTabA[iCount] = iA;
}
if (iLambda == iMaksLambda) {
iCount++;
iTabA[iCount] = iA;
}
}
}
}
for (int i = 0; i < iCount; i++) {
if (bfun_CheckWithTheory(iA, iPrimeNumbersTab, iModule) == true) {
iA = iTabA[i];
}
else {
iA = iTabA[iCount];
}
}
return iA;
}
