Evklid Alqoritmi#413

Evklid Alqoritmi

1 saniyə

122,174 meqabayt

Orta

Dmitrik informatika öyrənməyə yeni başlayıb. Onun öyrəndiyi ilk alqoritmlərdən biri, iki ədədin ən böyük ortaq bölənini (ƏBOB) tapmaq üçün Evklid alqoritmi idi. Xatırladaq ki, iki ədəd $a$ və $b$ üçün ƏBOB, həm $a$ , həm də $b$ ədədlərini qalıqsız bölən ən böyük təbii ədəd $x$ -dir.

Evklid alqoritmi belə işləyir:

$a$ və $b$ — ƏBOB tapılmalı olan ədədlərdir.
Əgər $b = 0$ b = 0 olarsa, $a$ ƏBOB-dur.
Əgər $b > a$ b > a olarsa, $a$ və $b$ ədədlərinin yerlərini dəyişmək lazımdır.
$a$ ədədinə $a - b$ a - b qiymətini mənimsətmək.
2-ci addıma qayıtmaq.

Dmitrik Evklid alqoritmini tez bir zamanda mənimsədi və onun köməyi ilə çoxlu ƏBOB-lər hesabladı. Tezliklə ona yeni bir məsələ həll etmək fikri gəldi. $a$ , $b$ , $c$ və $d$ ədədləri verilib. Verilmiş $(a, b)$ ədədlər cütü üçün Evklid alqoritminin icrası prosesində elə bir anın olub-olmadığını öyrənmək lazımdır ki, 2-ci addımın icrasından əvvəl $a = c$ a = c və $b = d$ b = d olsun.

Bu məsələni həll edən proqram yazın.

Giriş

Birinci sətir, giriş məlumat dəstlərinin sayı olan $k$ ( $1 \leq k \leq 100$ 1 \leq k \leq 100) ədədini ehtiva edir. Sonra bu dəstlərin təsviri gəlir. Hər təsvir iki sətirdən ibarətdir. Birinci sətir iki tam ədəd ehtiva edir: $a$ , $b$ ( $1 \leq a, b \leq 1 0^{18}$ 1 \leq a, b \leq 10^{18}). İkinci sətir isə iki tam ədəd ehtiva edir: $c$ , $d$ ( $1 \leq c, d \leq 1 0^{18}$ 1 \leq c, d \leq 10^{18}). Sətirdəki bütün ədədlər boşluqla ayrılmışdır.

Çıxış

Hər bir giriş məlumat dəsti üçün ayrıca sətirdə **YES** sözünü çıxarın, əgər Evklid alqoritminin $(a, b)$ ədədlər cütü üçün tətbiqi prosesində hər hansı bir anda $(c, d)$ cütu alınarsa, və ya **NO** sözünü çıxarın – əks halda.

Nümunələr

Nümunə 1

Loading

b = 0

b > a

a - b

a = c

b = d

1 \leq k \leq 100

1 \leq a, b \leq 1 0^{18}

1 \leq c, d \leq 1 0^{18}