Cerința

Mama vrea să acopere cu covoare o cameră cu lungimea de n metri și lățimea de m metri. Ea are la dispoziție oricâte covoare în formă de pătrat, de orice dimensiune, număr natural și respectă următoarele reguli:

• fiecare covor plasat are laturile paralele cu laturile camerei;
• covoarele așezate nu se suprapun;
• de fiecare dată se folosește cel mai mare covor care poate fi ales în acel moment;
• de fiecare dată covorul ales se plasează în așa fel încât zona neacoperită încă să fie un dreptunghi.

Știind dimensiunile camerei să se determine care este dimensiunea maximă a unui covor folosit și numărul total de covoare folosite.

Date de intrare

Programul citește de la tastatură numerele n și m, reprezentând dimensiunile camerei.

Date de ieșire

Programul va afișa pe ecran numerele L și N reprezentând în ordine dimensiunea maximă a unui covor folosit și numărul total de covoare folosite.

Restricții și precizări

• 1 ≤ n,m ≤ 1000000000
• dimensiunile covoarelor sunt numere naturale nenule

Exemplul 1

Intrare

10 3

Ieșire

3 6

Explicație

Camera are forma următoare:

Se folosesc 3 covoare de latură 3 și 3 covoare de latură 1. Dimensiunea maximă este 3. O modalitate de așezare a covoarelor este:

Exemplul 2

Intrare

1 100

Ieșire

1 100

Explicație

Se folosesc 100 covoare de latură 1. Dimensiunea maximă este 1.

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

int main()
{
    int a , b;
    cin >> a >> b;
    cout << min(a , b) << ' ';
    int cnt = 0;
    while(a!=0 && b!=0)
    {
        if(a > b)
        {
            int x = a/b;
            a-=(x*b);
            cnt += x;
        }
        else
        {
            int x = b/a;
            b-=(x*a);
            cnt += x;
        }
    }
    cout << cnt;
    return 0;
}