Szczegółowe omówienie zadania Wesoła małpka:

Link do powyższego omówienia zadania Wesoła małpka:
https://youtu.be/9pX9VAosgTY?t=2880
–
Optymalne rozwiązanie zadanie Wesoła Małpka przy pomocy NWW (Najmniejszej Wspólnej Wielokrotności):
https://youtu.be/9pX9VAosgTY?t=3543

——-
Link do treści zadania Wesoła małpka:
https://szkopul.edu.pl/problemset/problem/pZzE-qfzON1jZUCmbUdEbR1i/site

——
Zadanie Wesoła małpka pokazuje zastosowanie NWD i NWW w informatyce i algorytmice.
NWD – Największy Wspólny Dzielnik
NWW – Najmniejsza Wspólny Wielokrotność

#include <bits/stdc++.h>
using namespace std;

int ObliczNWD(int a, int b) {
  int reszta;

  while(b!=0) {
    reszta = a%b;
    a = b;
    b = reszta;
  }

    return a;
}

int main(){
 ios_base::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);

 int liczba_pytan, liczba_klatek, skok;
 int iloczyn, nwd_liczb, wynik;
 int i;

 cin >> liczba_pytan;
 for (i=1; i<=liczba_pytan; ++i) {
    cin >> liczba_klatek >> skok;
    nwd_liczb = ObliczNWD(liczba_klatek,skok);
    wynik = liczba_klatek / nwd_liczb;
    cout << wynik << "\n";
 }

 return 0;
}