Module: (بايثون) التدريب العملي 4. خوارزمية إقليدس

Problem

تعلم طلاب الصف الخامس بيتيا وفانيا خوارزمية إقليدس التالية في فصل الرياضيات:

1. دع & nbsp؛ a ، & nbsp؛ b & nbsp؛ & mdash؛ الأرقام التي سيتم العثور عليها.

2. If & nbsp؛ b & nbsp؛ = & nbsp؛ 0 ثم number & nbsp؛ a & nbsp؛ & mdash؛ GCD الذي تبحث عنه.

3. إذا & nbsp؛ b & gt؛ & nbsp؛ a ثم بدل الأرقام & nbsp؛ a & nbsp؛ and & nbsp؛ b . < / ص>

4. تعيين قيمة & nbsp؛ a & nbsp؛ a & nbsp؛ & ndash؛ & nbsp؛ b .

5. ارجع إلى الخطوة 2.

توصل ماشا إلى مهمة لإصلاحها. طلبت من الأولاد الخروج بمثل هذه الأرقام & nbsp؛ a ، & nbsp؛ b ، & nbsp؛ c & nbsp؛ and & nbsp؛ d التي عملية تنفيذ خوارزمية إقليدس لزوج معين من الأرقام (a، & nbsp؛ b) ، تأتي لحظة قبل تنفيذ الخطوة 2 ، يكون الرقم & nbsp؛ a على

اكتب برنامجًا لـ Masha للتحقق مما إذا كانت الأرقام ترضي a ، b ، c ، d شروط ماشا. الإدخال: يحتوي السطر الأول من الإدخال على عدد حالات الاختبار & nbsp؛ K & nbsp؛ ( \ (1 & lt؛ = K & lt؛ = 100 \) ). فيما يلي وصف لهذه المجموعات. كل وصف يتكون من سطرين. يحتوي الأول على رقمين صحيحين: & nbsp؛ a ، & nbsp؛ b & nbsp؛ ( \ (1 & lt؛ = a، \ ب & lt؛ = 10 ^ {18} \) ). السطر الثاني - رقمان صحيحان: & nbsp؛ c ، & nbsp؛ d & nbsp؛ ( \ (1 & lt؛ = c، \ d & lt؛ = 10 ^ {18} \) ).
جميع الأرقام في السطور مفصولة بمسافات.

الإخراج: & nbsp؛ لكل حالة اختبار ، أخرج الكلمة "إذا كان أثناء تطبيق خوارزمية Euclid إلى زوج من الأرقام ( a ، & nbsp؛ b ) في وقت ما يتم الحصول على زوج ( c ، & nbsp؛ d < / كود>). وإلا ، فقم بإخراج الكلمة & quot؛ NO & quot ؛.

نبسب ؛