Algorytm Euklidesa

31.10.2009 - Damian Rusak
Trudność

Zadania

Zastanów się nad dwoma poniższymi problemami (możesz wysłać do nich rozwiązanie na sprawdzaczkę).

1. Mamy liczbę pierwszą $ p $, oraz liczbę całkowitą dodatnią $ a $, $ a \bot p $. Jak znaleźć taką liczbę całkowitą dodatnią $ b $, $ b \leq p-1 $, taką, że $ p \mid ab - 1 $ ?. (Taką liczbę nazywamy odwrotnością $ a $ w modulo p).

2. Rozważmy wspominany problem aptekarza, z jednym dodatkiem - aptekarz chciałby użyć jak najmniej odważników. Jak znaleźć takie rozwiązanie?

Poniżej znajdują się dokładne specyfikacje tych zadań i okienka do wysłania rozwiązań. Zachęcamy do spróbowania swoich sił!

 

 


Zadanie Monety

Limit czasowy: 1s; Limit pamięciowy: 16 MB

Aptekarz Joe bardzo lubi liczyć bilon z kasy w swojej aptece. Dzisiaj wpadł na pomysł, aby wziąć sobie dwie monety o pewnych nominałach i znaleźć taką kwotę, którą można wypłacić zarówno za pomocą dowolnej ilości monet pierwszego rodzaju jak i za pomocą dowolnej ilości monet drugiego rodzaju. Joe nie jest zbyt inteligentny, poprosił więc Cię o pomoc. Napisz program, który znajdzie dla niego taką kwotę!

Wejście:

Pierwsza linia wejścia składa się z jednej liczby całkowitej $ n $ $ \left(1 \leq n \leq 1000\right $, oznaczającej ilość testów do rozważenia. W kolejnych $ n $ liniach znajdują się pary liczb całkowitych $ a_{i} $, $ b_{i} $ $ \left(1 \leq a_{i}, b_{i} \leq 10000\right) $.

Wyjście:

Dla każdej pary należy na wyjściu wypisać jedną linię z jedną liczbą - najmniejszą taką kwotą, którą można wypłacić zarówno za pomocą nominału $ a_{i} $ jak i $ b_{i} $.

Przykład:

Dla wejścia:

3
10 6
36 60
1 1

Poprawne wyjście to:

30
180
1
Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.

 

 


Odwrotność

Limit czasowy: 1s; Limit pamięciowy: 16MB

Liczby pierwsze mają bardzo dużo ciekawych właściwości. Jedną z nich jest to, że każda liczba całkowita, mniejsza od danej liczby pierwszej, ma swoją unikalną odwrotność - czyli taką liczbę, że te dwie wymnożone dają resztę 1 z dzielenia przez tę liczbę pierwszą. Napisz program, który odnajduje takie odwrotności.

Wejście:

Pierwsza linia wejścia zawiera dwie liczby całkowite $ n $ i $ p $, $ \left(1 \leq n \leq 1000, 2 \leq p \leq 1000000 \right) $. W kolejnych n liniach znajduje się po jednej liczbie $ a_{i} $, $ \left(1 \leq a_{i} \leq p-1\right) $.

Wyjście:

Dla każdej liczby $ a_{i} $ należy wypisać jej odwrotność - liczbę całkowitą dodatnią $ b_{i} $, mniejszą od $ p $, taką ,że $ p \mid a_{i}\cdot b_{i} - 1 $.

Przykład:

Dla wejścia:

3 7
5
6
2

Poprawne wyjście to:

3
6
4
Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.

 

 


 

Rozterki aptekarza

Limit czasowy: 1s; Limit pamięciowy: 16MB

Aptekarz Joe chce odmierzyć $ d $ gramów substancji. Ma do dyspozycji dwa rodzaje odważników - o wadze $ a $ i wadze $ b $, oraz wagę szalkową. Chciałby odważyć $ d $ gramów i przy okazji użyć do tego celu jak najmniej odważników. Joe wie, że $ d $ jest największym wspólnym dzielnikiem $ a $ i $ b $. Pomóż mu!

Wejście:

W pierwszej linii wejścia znajduje się jedna liczba całkowita $ n $, $ \left(1 \leq n \leq 1000\right) $, oznaczające ilość zestawów testowych. W kolejnych $ n $ liniach znajdują się pary liczb całkowitych $ a_{i} $, $ b_{i} $ , $ \left(1 \leq a_{i}, b_{i} \leq 10000\right) $. Są to wagi dwóch odważników. Wiadomo, że Joe chce za ich pomocą odważyć $ d_{i} $ - największy wspólny dzielnik $ a $ i $ b $.

Wyjście:

Dla każdego zestawu testowego należy wypisać jedną linię, zawierającą najmniejszą liczbę odważników, potrzebnych do odważenia $ d_{i} $ gramów substancji.

Przykład:

Dla danych wejściowych:

2
10 8
1 11

Poprawne wyjście to:

2
1

Objaśnienie: $ NWD\left(10,8\right) = 2 $, $ 10 - 8 = 2 $, więc potrzeba co najmniej dwóch odważników. W drugim przykładzie wystarczy jeden odważnik o wadze 1.

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
4.208335
Twoja ocena: Brak Ocena: 4.2 (24 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com