Ալգորիթմներ և Տվյալների Կառուցվածքներ

Ամենամեծ ընդհանուր բաժանարար (GCD) - Էվկլիդեսի ալգորիթմ

Մի քանի անգամ ալգորիթմը գործարկելուց հետո կարելի է նկատել, որ որոշ գործողություններ ավելորդ են, և ամենամեծ ընդհանուր բաժանարար (GCD) գտնելու ալգորիթմը հնարավոր է օպտիմիզացնել։
Հանելով ամենամեծ ընդհանուր բաժանարար գտնելու տարբերակում անընդհատ հանում ենք փոքր թիվը մեծ թվից, մինչև ստանանք 0 կամ վերջնական պատասխանին հավասար թիվ։ Այդ գործընթացը կարելի է արագացնել, եթե մեծ թիվը բաժանենք փոքր թվի վրա ու խնդիրը լուծենք մնացորդով։ Մոդուլո (modulo) գործողության դեպքում մեծ թիվը անընդհատ բաժանվում է փոքր թվի վրա, ու վերցվում է մնացորդը, մինչև ստացվի 0։ Վերջին ոչ զրոյական մնացորդը հանդիսանում է ամենամեծ ընդհանուր բաժանարարը (GCD)։
Մոդուլո գործողությունը պարզապես ավելի արդյունավետ միջոց է GCD գտնելու համար։ Բազմաթիվ անգամ մեծ թվից փոքրը հանելու փոխարեն, դուք բաժանում եք այդ թվերը իրենց ընդհանուր բաժանարարներով, ու արդյունքում շատ ավելի արագ եք մոտենում մեծագույն ընդհանուր բաժանարարին։
a, b = int(input()), int(input())
while a > 0 and b > 0:  # Եթե a-ն կամ b-ն 0 են, ապա մյուսը կլինի GCD
    a, b = b, a % b     # (a, b)-ի GCD-ն հավասար է (b, a % b)-ի GCD-ին

d = b if a == 0 else a  # եթե a-ն 0 է, ապա b-ն է GCD, իսկ եթե b-ն է 0, ապա a-ն է GCD
print('gcd:', d)
Այս ալգորիթմը առաջին անգամ հիշատակվել է Էվկլիդեսի գրքում, որը գրվել է մ.թ.ա. մոտ 300 թվականին։
 
Եկեք դիտարկենք ալգորիթմի աշխատանքի մի քանի օրինակ.
a = 8, b = 12
  1. a = 12, b = 8
  1. a = 8, b = 4
  1. a = 4, b = 0
  1. break ⇒ GCD = 4
a = 54, b = 24
  1. a = 24, b = 6
  1. a = 6, b = 0
  1. break ⇒ GCD = 6
a = 17, b = 16
  1. a = 16, b = 1
  1. a = 1, b = 0
  1. break ⇒ GCD = 1

Մուտք

Մուտքի միակ տողում տրված են երկու ամբողջ թվեր a և b (0 ≤ a, b ≤ )։

Ելք

Ծրագիրը պետք է տպի a և b-ի ամենամեծ ընդհանուր բաժանարարը (GCD)։

Օրինակներ

Input
Output
8 12
4
54 24
6
17 16
1

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue