#include<iostream>
#include<cstdlib>
#include<vector>
#include<math.h>

using namespace std;

void sito(bool *tab, unsigned int n)
{
	for (int i=2; i*i<=n; i++) //przeszukujemy kolejnych kandydatów na pierwsze
    {							//wystarczy sprawdziæ do pierwiastka z n
    							// i<=sqrt(n) - podnosz¹c do kwadratu mamy
    							// i*i <= n
        if(!tab[i])				//jesli liczba jest pierwsza(ma wartosc 0)
		for (int j = i*i ; j<=n; j+=i) //to wykreslamy jej wielokrotnosci
            tab[j] = 1;			//ustawiaj¹c wartosæ na 1
    }
}
/*
int x, y;
void euklides(int a, int b)
{
	if(b!=0)
	{
		euklides(b, a%b);

		int pom = y;
		y = x  - a/b*y;
		x = pom;
	}
}
*/

/*
int x,y;
int r_count =1;
void euklidesAlgorithm(int a , int b)
{
     int q, r;

     r = a % b;

        if(r!=0 ){
            cout<< "r"<<r_count<<" "<< r <<endl;
            r_count++;

            euklidesAlgorithm(b, r);
            int q = y;
            y = x-a / b*y;
            x = q;

        }*/
        /*
int rCounter = 1;
int euklidesAlgorithm(int a, int b, int& x, int& y, bool start){

    static int staticX[2] = {};
	static int staticY[2] = {};
    int q, r, r2, q2;

    r = a % b ;
    q = (a - r) / b;
    cout<< "r"<<rCounter<<" = "<<a << " - "<< q<< " * "<< b<< " = "<< r<< "\n";
    rCounter++;
    if( r != 0){
        return euklidesAlgorithm(b , r);
    }
    return b;
}*/


int euklidesAlgorithm(int a, int b, int& x, int& y, bool start= true)
{
	static int staticX[2] = {};
	static int staticY[2] = {};

	int r = a % b;
	int q = (a - r) / b;

	std::cout << a << " = " << q << " * " << b << " + " << r << "\n";

	if (r != 0) {
		// Wyczyść wartości x i y, jeśli jest to pierwsze wywołanie funkcji
		if (start) {
			staticX[0] = 0;
			staticX[1] = 1;
			staticY[0] = 1;
			staticY[1] = -q;
		}
		else {
			int tempX = staticX[1];
			staticX[1] = staticX[0] - staticX[1] * q;
			staticX[0] = tempX;

			int tempY = staticY[1];
			staticY[1] = staticY[0] - staticY[1] * q;
			staticY[0] = tempY;
		}

		std::cout << "x = " << staticX[1] << " y = " << staticY[1] << "\n\n";

		return euklidesAlgorithm(b, r, x, y, false);
	}

	x = staticX[1];
	y = staticY[1];

	return b;
}




    /* cout<< a/b<<endl;
     r1 = a%b;
     cout<< " r1  = "<< r1;
     r2 = b%r1;
     cout<< " r2  = "<< r2<<endl;
     r3 = r1%r2;
      cout<< " r3  = "<< r3<<endl;
      q1= (a -r1)/b;
      cout<< " q1: " <<q1<<endl;
      q2 = (b-r2)/r1;
      cout<<"q2 = "<< q2<<endl;
      q3 = (r1- r3) / r2<<endl;
      cout<< "q3 = "<<q3<<endl;


}
*/

int decToBinSize(int dec)
{
	for (int i = 0; ; i++) {
		if (pow(2, i) > dec) {
			return i;
		}
	}
}

std::vector<bool> decToBin(int dec)
{
	int size = decToBinSize(dec);
	std::vector<bool> bin;

	for (int i = size - 1; i >= 0; i--) {
		if (pow(2, i) <= dec) {
			dec -= pow(2, i);
			bin.push_back(1);
		}
		else {
			bin.push_back(0);
		}
	}

	return bin;
}

unsigned long long int modulo(unsigned long long int a, const unsigned long long int b, unsigned long long int c)
{
	std::vector<bool> binB = decToBin(b);
	int binSize = decToBinSize(b);

	unsigned int currentNumber = a; // pow(a, 1)
	currentNumber %= c;

	unsigned long long int result = 1;

	if (binB[binSize - 1] == 1) {  // binb to potega zapisana w formie binarnej
		result *= currentNumber;
		result %= c;
	}

	for (int i = 1; i < binSize; i++) {
		currentNumber = pow(currentNumber, 2);
		currentNumber %= c;

		if (binB[binSize - 1 - i] == 1) {
			result *= currentNumber;
			result %= c;
		}
	}

	return result;
}


int main()

{
    //int x, y;
    //cout<< " \nWpisz liczbe  a i b"<<endl;
    //int a = 1920;
    //int b = 162;
    //int result  = euklidesAlgorithm(a,b,x,y );

    //cout<< "NWD ( "<<a<<", "<<b<< " )"<<" = "<< result;

    cout << modulo(30, 2, 42) << endl;

    int finalNumber;
	bool *tab;

	cout<<"Podaj zakres górny przedzia³u: ";
	finalNumber=2800000;

	tab = new bool [finalNumber+1];
	for(int i=2; i<=finalNumber; i++) //zerowanie tablicy
		tab[i] = 0;

	sito(tab, finalNumber); //przesianie liczb

	cout<<"Kolejne liczby pierwsze z przedzia³u [2.."<<finalNumber<<"]: ";
    int primecounter=0;

    int p = 0;
    int q = 0;
    cout<< "Wpisz liczbe 1: "<<endl;
    int n1;
    cin>>n1;
    cout<< "Wpisz liczbe 2: "<<endl;
    int n2;
    cin>>n2;
    unsigned long long int liczba;
	for(int i=2;i<=finalNumber;i++)
		if(!tab[i] && (p == 0 || q == 0)){
		//	cout<<i<<" ";
            liczba=i;
			primecounter++;
			if (primecounter == n1)
                p = liczba;
            if (primecounter == n2)
                q = liczba;
		}

    int n = p*q;
    cout << "n=" << n << endl;

    int m = (p-1)*(q-1);
    cout << "m=" << m << endl;

    int e,x,y;
    do
    {
        cout<< "Podaj losowa liczbe z przedzialu <1;" << m << ">:";
        cin>>e;
    } while(e < 1 || e > m || euklidesAlgorithm(e, m, x, y) != 1);

    cout << "x=" << x << endl;

    int d, s, t;

    cout<< "Podaj t: ";
    cin>>t;

    if (x > 0)
    {
        d = x;
        cout << "d = " << d << endl;
    }

    cout << "t " << t << " e " << e << " n " << n << endl;
    s = modulo(t, e, n);
    cout << "s = " << s << endl;

    t = modulo(s, d, n);
    cout << "t = " << t << endl;

    //cout<< endl;
    //cout<<"N-ta liczba pierwsza:  "<< liczba;

	delete []tab;


    /*
    x = 1, y = 0;
	int a, b;

	cout<<"Podaj liczby: ";
	cin>>a>>b;

	euklides(a, b);

	cout<<"nwd("<<a<<", "<<b<<") = "
	<<a<<" * "<<x<<" + "<<b<<" * "<<y<<" = "
	<<a*x+b*y<<endl;
*/


/*
	int n;
	bool *tab;

	cout<<"Podaj zakres górny przedzia³u: ";
	n=2800000;

	tab = new bool [n+1];
	for(int i=2; i<=n; i++) //zerowanie tablicy
		tab[i] = 0;

	sito(tab, n); //przesianie liczb

	cout<<"Kolejne liczby pierwsze z przedzia³u [2.."<<n<<"]: ";
    int primecounter=0;

    cout<< "Wpisz liczbe n: "<<endl;
    int d;
    cin>>d;
    unsigned long long int liczba;
	for(int i=2;i<=n;i++)
		if(!tab[i] && primecounter<d){
		//	cout<<i<<" ";
            liczba=i;
			primecounter++;
		}

    cout<< endl;
    cout<<"N-ta liczba pierwsza:  "<< liczba;

	delete []tab;*/

	cin.get();

	system("pause");
    return 0;
}