Ограничение на выполение кода по времени: 0.2 секунда
Ограничение по памяти: 64 мегабайта
Наверное всем известен алгоритм Евклида, который заключается в следующем:
1. Пусть a и b — числа, НОД которых надо найти.
2. Если b = 0, то число а — искомый НОД.
3. Если b > а, то необходимо поменять местами числа a и b.
4. Присвоить числу а значение а — b.
5. Вернуться к шагу 2.
Вам требуется узнать, наступит ли в процессе реализации алгоритма Евклида для заданной пары чисел (а,b) такой момент, когда перед исполнением шага 2 число a будет равно числу с, а число b
будет равно d.
Формат входных данных:
Первая строка входных данных содержит число К — количество проверок, которые надо выполнить (1 ≤ К ≤ 100).
Далее следует К блоков. Каждый блок состоит из двух строк: первая содержит пару чисел (а,b),
а вторая — пару чисел (с, d). Все эти числа — натуральные и не превосходят 10^18.
Формат выходных данных:
Для каждого блока входных данных выведите УES, если в процессе применения Алгоритма Евклида к паре (a,b) в какой-то момент получится пара (с, d). В противном случае выведите NO.
Ответы
Ответ:
Объяснение:
Для решения данной задачи на проверку наступления момента, когда число a станет равным c, а число b станет равным d, можно использовать сам алгоритм Евклида. Ниже представлен код на C++, который решает задачу с учетом ограничений по времени и памяти:
#include <iostream>
typedef long long ll;
ll gcd(ll a, ll b) {
if (b == 0) {
return a;
}
if (b > a) {
std::swap(a, b);
}
return gcd(a - b, b);
}
int main() {
int K;
std::cin >> K;
for (int i = 0; i < K; ++i) {
ll a, b, c, d;
std::cin >> a >> b >> c >> d;
ll gcd_ab = gcd(a, b);
if (gcd_ab == gcd(c, d)) {
std::cout << "YES" << std::endl;
} else {
std::cout << "NO" << std::endl;
}
}
return 0;
}
Программа считывает число K, количество проверок, которые необходимо выполнить. Затем она считывает K блоков с парами чисел (a, b) и (c, d). Для каждого блока она вычисляет НОД для пары (a, b) с помощью функции gcd, и сравнивает его со значением НОД для пары (c, d). Результат выводится на экран (YES, если значения совпадают, и NO в противном случае).
Пожалуйста, учтите, что данное решение использует рекурсивную реализацию алгоритма Евклида, которая может привести к превышению ограничений по глубине стека при больших значениях чисел a и b. Если вам необходимо обработать такие случаи, то рекомендуется использовать итеративную реализацию алгоритма Евклида или алгоритм Бинарного gcd.