Mistrzostwa Polski Szkół Średnich w Programowaniu Zespołowym 2024

2020-2022 2023 Regulations Schedule RODO info Ranking

Problem description

.desc_header { margin-bottom: 2em; text-align: center; } .desc_title { font-size: 200%; text-decoration: underline; padding: 0em 0.2em; display: inline-block; } .desc_code { padding: 0em 0.2em; font-weight: bold; display: inline-block; } .desc_meta { margin: 0.5em; } .desc_memlimit { padding: 0em 1.25em; display: inline-block; } .desc_timelimit { padding: 0em 1.25em; display: inline-block; } .desc .example-test { width: 100%; margin-top: 10px; } .desc .example-test td { vertical-align: top; } .desc .example-test pre { margin-top: 5px; } Ile odejmowań? (euclid-subs) Memory limit: 64 MB Time limit: 1.00 s Analizujemy naiwny algorytm Euklidesa. Naiwny algorytm Euklidesa dla danych liczb A oraz B działa w następujący sposób: jeśli A ≥ B, przechodzi z NWD(A,B) → NWD(A−B,B), jeśli A < B, przechodzi z NWD(A,B) → NWD(B,A). Algorytm kończy swoje działanie, jeśli którakolwiek z liczb jest równa 0. Ile razy nastąpi pierwsze przejście tego algorytmu (czyli odejmowanie) dla zadanych A i B? Wejście W pierwszym (jedynym) wierszu wejścia znajdują się dwie liczby naturalne oddzielone pojedynczym odstępem A oraz B. Wyjście W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć liczba kroków z odejmowaniem, które wykona naiwny algorytm Euklidesa dla A oraz B. Ograniczenia 0 ≤ A, B ≤ 1018. Przykład Input Output 6 17 8