#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
void DzielenieReszta(int a, int b);
int NWD(int a, int b);
int NWD2(int a, int b);
int NWD3(int a, int b);
int NWW(int a, int b);
int fib(int n);
int licznik = 0, licznik2 = 0, licznik3 = 0;
int  main()
{
        DzielenieReszta(7, 2);
        int n = 8;
        int n2 = n+1;
        cout<<fib(n) << " fiba od n"<< endl;
        cout<<fib(n2)<<" fiba od n2" << endl;
        cout << NWD(fib(n),fib(n2)) << " ";
        cout<<licznik<< " nwd z dodawaniem"<<endl;
        cout << NWD2(fib(n), fib(n2)) << " ";
        cout<< licznik2 << " nwd z mnozeniem"<<endl;
        cout << NWD3(fib(n), fib(n2)) << " ";
        cout<< licznik3 << " nwd rekurencyjnie"<<endl;
        cout << NWW(fib(n), fib(n2)) << " nww" << endl;
        return 0;
}

void DzielenieReszta(int a, int b)
{
        int r = a;
        if (b == 0)
        {
                cout << "b jest rowne 0!" << endl;
                return;
        }
        int q = 0;
        while (r>=q)
        {

                q++;
                r = r - b;
        }
        cout << q <<"*" <<b <<"+" << r <<  "   dzielenie z reszta"<<endl;
}
int NWD(int a, int b)
{
        while (a != b)
        {
                ++licznik;
                if (a < b)
                        b = b - a;
                else
                        a = a- b;

        }
        return a;
}
int NWD2(int a, int b)
{
        int t = 0;

        while (b != 0)
        {
                ++licznik2;
                t = b;
                b = a % b;
                a = t;

        }
        return a;
}