# Przydatne informacje z OBOZU C++
Największy Wspólny Dzielnik (NWD)

Dla zadanych liczb a,b
chcemy znaleźć najwiekszą liczbę c taką, że dzieli ona zarówno a jak i b

. Na przykład NWD(18, 24) = 6 oraz NWD(6, 8) = 2.

## Obserwacja 1
Łatwo zauważyć, że każda liczba dzieli 0
, więc dla każdego a zachodzi **NWD(a,0)=a**

## Twierdzenie 1
Jeśli c
jest największym wspólnym dzielnikiem a,b oraz a≤b, to c jest też największym wspólnym dzielnikiem a−b,b.
Zapisane inaczej:
**NWD(a,b)=NWD(a−b,b)**

## Obserwacja 2
Weźmy a=23
oraz b=4. Wtedy z poprzedniego twierdzenia:
NWD(23,4)=NWD(19,4)=NWD(15,4)=NWD(11,4)=NWD(7,4)=NWD(3,4)
Zauważmy, że to samo możemy osiągnąć w jednej operacji zamiast odejmowania robiąc modulo, bo 23%4=3

## Twierdzenie 2
**NWD(a,b)=NWD(a%b,b)**

Algorytm (Euklidesa)
Mamy dwie zmienne a,b
. Zamieniamy je miejscami tak, aby w a była większa liczba, a w b mniejsza. Potem w pętli dopóki obie są różne od 0 robimy a=a%b, a następnie (skoro nasze nowe a jest mniejsze od b) zamieniami te zmienne miejscami. Kiedy jedna z tych zmiennych jest równa 0

, przerywamy pętlę i wypisujemy drugą liczbę jako NWD.

## NWW
Mając NWD umiemy obliczyć Najwiekszą Wspólną Wielokrotność (NWW) dwóch liczb ze wzoru:
**NWW(a,b)=(a⋅b)/NWD(a,b)**

# Zmienne znakowe i napisy
## Zmienne typu char(acter)

W C++ mamy do dyspozycji typ dla zmiennych znakowych. W zmiennych tych mogą być trzymane wartości z zakresu [−128,127]

. Funkcje wyjścia/wejścia interpretują odpowiednio typ znakowy, wypisując zamiast znajdującej się w zmiennej liczbę, odpowiadający tej liczbie znak z tabeli ASCII.
## Znak a liczba

Skoro wiemy, że znaki to tak naprawdę liczby, nie musimy pamiętać wartości tablicy ASCII. W kodzie znak traktowany jest po prostu jak liczba typu char.
Przykład:

'!' + '$' == 33 + 36 == 69 == 'E'

Sprawdzanie wielkości litery

char c;
cin>>c;

if(c >= 'a' && c <= 'z')
    cout<<"mala litera\n";
else if (c >= 'A' && c <= 'Z')
    cout<<"wielka litera\n";
else
    cout<<"nie litera\n";

Zamiana wielkiej litery na małą

cin>>c; //zakładamy tu, że c to znak o wartości pomiędzy [65, 90]

c = c + 32;
cout<<c<<'\n';

Zamiana cyfry na liczbę

char c;
cin>>c; //zakładamy tu, że c to znak o wartości pomiędzy [48, 57]

int a = c - '0';

# Tablice dwuwymiarowe

int tab[n][m] oznacza, że deklarujemy tablicę wielkości nxm, gdzie n interpretujemy jako liczba wierszy, a m jako liczba kolumn.

Poniżej znajduje się przykładowy kod do tablic dwuwymiarowych:

#include <iostream>
using namespace std;
int tab[100][100];
int wie = 100, kol=100;
int main(){
    int licznik=0;
    for(int w=0; w<wie; w++){
      for(int k=0; k<kol; k++){
        tab[w][k]=licznik;
        licznik++;
      }
    }
    for(int w=0; w<wie; w++){
        for(int k=0; k<kol; k++){
          cout<<tab[w][k]<<" ";
      
        }
        cout<<"\n";
    }
}

## O macierzach:

Macierz to tablica dwuwymiarowa.
Macierze można dodawać, odejmować i mnożyć przez liczbę.

## Wskazówki do kodu:

Lepiej pisać zmienne w taki sposób, żeby od razu było wiadomo, co oznaczają:

int wiersze;// liczba wierszy
int kolumny; // liczba kolumn

albo

int wie; //liczba wierszy
int kol; //liczba kolumn

Jeśli zadanie nie wymaga innego sposobu - najlepiej jest iterować się najpierw po wierszach a potem po kolumnach:

    for(int w=0; w<wie; w++){
        for(int k=0; k<kol; k++){
          //wasz kod
        }
    }

# Tablice jednowymiarowe

## Tablice domyślnie deklarujemy w przestrzeni globalnej.

Przykłady:

#include <iostream>
using namespace std;
// (przestrzeń globalna)

// np. dla n <= 10^6
int tab[1000006]; // <- zawsze deklarujemy trochę więcej niż potrzebujemy
// ↑ tablice tworzone w przestrzeni globalnej są wyzerowane.

// ciekawostka, że tak można
const int P = 1e6+6;
int tab2[P];

// za pomocą nawiasów klamrowych,
// można przypisywać wartości do tablicy przy jej tworzeniu.
int test[3]={1,2,3}; 

int main(){
    int c; // <- UWAGA! Zmienna bez zainicjalizowanej wartości
    int tab3[100]={}; // <- tak też stworzymy wyzerowaną tablicę
    // jednkaże zwykle nie deklarujemy dużych tablic w funkcjach,
    // a w przestrzeni globalnej
    
    // ❌ TAK NIE ROBIMY:
    tab3[100] = 3;   // <- tab3 ma zakres od 0 do 99
    cout<<tab3[105]; // <----------------------------
    
    tab = 7; // tab to wskaźnik na tablicę, a nie zmienna!
    cout<<tab; //<- to nie wypisze nam całej tablicy :(
    
    int n;
    cin>>n;
    int tab4[n]; // NIE WOLNO TAK ROBIĆ! W języku C jest to nielegalne.
    
...

# Warto wiedzieć!

Typ int ma 4 bajty = 32 bity.
W zmiennej typu int możemy trzymać liczby od −231

(~ -2mld.) do 231−1

(~ 2 mld.)
Trzeba pamiętać, że gdy nie przypisujemy wartości danej komórce pamięci, to znajduje się tam losowa wartość (tak jak znak zapytania w maszynie RAM).
Zadania na Themisie i na konkursach często mają limit pamięci. Jednym z przeliczników, które warto znać jest ten, że tablica miliona intów ma rozmiar 4MB.
Deklarując tablicę musimy pamiętać o jej odpowiedniej wielkości. Nie możemy jako programiści dopuścić do zaglądania w “nie naszą pamięć”. Np. próba odczytu lub zapisu do komórki spoza tablicy, w zadaniu na Themisie, np. tab[-1], lub tab[10] (dla tablicy 10 elementowej), zakończy się odpowiednim błędem.
Próba zapisu liczby o typie innym niż zmienna do której zapisujemy, nie zakończy się błędem. Program wykona swoje zadanie, odpowiednio ucinając liczbę, lub modyfikując ją w inny sposób.
Np. cout<<(int)(3.5); wypisze liczbę 3.
By przyspieszyć działanie programu poprzez wyłączenie synchronizacji strumieni (i innych niepotrzebnych nam elementów) dodajemy na początku funkcji main linijki:

ios_base::sync_with_stdio(false);
cin.tie(0);