00021 - 804 - Gra Euklidesa - www.pl.spoj.com

Treść zadania:

Gra Euklidesa przebiega według następujących zasad:

•W grze bierze udział dwóch graczy (A i B). Początkowo każdy z nich dysponuje pewną niezerową liczbą identycznych żetonów - odpowiednio a i b.
•Jeżeli jeden z graczy ma mniej żetonów niż drugi, może wykonać ruch. Wykonując ruch, gracz zabiera partnerowi tyle żetonów, ile sam posiada. Żetony te są wyłączone z dalszej gry (tj. gracz wykonujący ruch ich nie przejmuje).
•Gra kończy się w sytuacji, gdy żaden z graczy nie może wykonać ruchu (w szczególności gra może skończyć się bezpośrednio po "rozdaniu" żetonów, bez jakichkolwiek ruchów).

Znając początkowe zasoby graczy (tj. wartości a i b), wyznacz łączną liczbę żetonów pozostałych w grze w chwili jej zakończenia.

Wejście
t [1 <= t <= 10; liczba partii]
a1 b1 [1 <= a1, b1 <= 1 000 000 000; początkowe liczby żetonów u graczy (partia #1) ]
a2 b2 [ jw. (partia #2) ]
...
at bt

Wyjście
r1 [ łączna liczba żetonów u obu graczy po zakończeniu partii #1 ]
r2 [ jw., dla partii #2 ]
...
rt

Przykład

Wejście:
3
1 1
2 4
9 6

Wyjście:
2
4
6

Kod źródłowy w C:

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int a, b, t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&a,&b);
        if(a==b)
        {
            printf("%d\n",a+b);
        }
        else
        {
            while(a!=b)
            {
                if(b%a==0)
                {
                    printf("%d\n",2*a);
                    break;
                }
                if(a%b==0)
                {
                    printf("%d\n",2*b);
                    break;
                }
                if(a<b)
                {
                    b=b%a;
                }
                else
                {
                    a=a%b;
                }
            }
        }
    }
    return 0;
}

Kod źródłowy w C++:

#include <iostream>

using namespace std;

int main()
{
    int a, b, t;
    cin>>t;
    while(t--)
    {
        cin>>a>>b;
        if(a==b)
        {
            cout<<a+b<<endl;
        }
        else
        {
            while(a!=b)
            {
                if(b%a==0)
                {
                    cout<<2*a<<endl;
                    break;
                }
                if(a%b==0)
                {
                    cout<<2*b<<endl;
                    break;
                }
                if(a<b)
                {
                    b=b%a;
                }
                else
                {
                    a=a%b;
                }
            }
        }
    }
    return 0;
}

Źródło:
http://pl.spoj.com/problems/EUCGAME/