Алгоритм Евклида

При решении данной задачи следует учитывать следующее. Поскольку ограничения на числа a, b, c, d в этой задаче достаточно большие, простая симуляция описанного в условии алгоритма не будет укладываться в ограничения по времени.

Опишем более быстрый алгоритм решения данной задачи. Разобьем процесс применения алгоритма Евклида к паре чисел (a, b) на фазы. Началом фазы будем считать обмен на шаге 3, а окончанием – момент перед следующим таким обменом (или окончание работы алгоритма – для последней фазы). Нетрудно видеть, что, если в начале фазы a=a₀, b=b₀, то в ее конце a=a₀ mod b₀, b=b₀. В то же время на каждом шаге внутри фазы из a вычиталось b₀, т.е. a последовательно было равно a₀, a₀-b₀, a₀-2b₀, …, a₀ mod b₀.

Для того чтобы проверить, встречалась ли пара (c, d) во время фазы, надо проверить следующие условия:

1. d=b₀
2. c – (a₀ mod b₀) делится на b₀
3. с ≤ a₀

В задаче необходимо проверить несколько наборов чисел a, b, c и d. Но здесь мы рассмотрим алгоритмическую реализацию лишь для одной такой четверки, т.к. обработка целого набора таких данных не представляет никакой сложности в реализации.

    int a,b,c,d;

    read(a,b,c,d);

    while(b > 0){
      if(a=c and b=d) break;
      if(b > a) a<-->b ;
      if(b > 0){
        if(b=d and a>=c and c>=a mod b and (c - a mod b) mod b=0) break;
        a:= a mod b;
      end;
    }
    
    if(b>0) write('YES') else write('NO');

[Обсуждение] [Все попытки] [Задача]