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

Ամենամեծ ընդհանուր բաժանարար (GCD) հանման միջոցով

Տրված են երկու դրական ամբողջ թվեր a և b: պահանջվում է հաշվել դրանց ամենամեծ ընդհանուր բաժանարարը: Այս անգամ թվերը կարող են լինել շատ մեծ, ուստի ամեն մի թվի բոլոր բաժանարարները գտնելը և ամենամեծն ընտրելը հնարավոր չէ։ Մենք պետք է օպտիմիզացնենք ալգորիթմը։
Ենթադրենք a > b։ Եթե դիտարկենք որևէ ընդհանուր բաժանարար d, ապա և՛ a-ն, և՛ b-ն բաժանվում են d-ի վրա։ Այդ դեպքում.
որտեղ x-ը և y-ը ամբողջ թվեր են։ Եթե a-ից հանենք b-ն, ապա կստանանք:
 
Ուրեմն, քանի որ d-ն և a-ի, և b-ի բաժանարար է, իսկ x-ն ու y-ը ամբողջ թվեր են, ապա x - y նույնպես ամբողջ թիվ է։ Հետևաբար a - b = d(x-y) նշանակում է, որ d-ն նաև a-b-ի բաժանարար է։ Այս դիտարկումը շատ օգտակար է և մեզ հնարավորություն է տալիս ծրագիրը դարձնել ավելի արագ։
Եթե և a-ն, և b-ն, և a-b-ն բաժանվում են ամենամեծ ընդհանուր բաժանարար d-ի վրա, ապա մենք կարող ենք d-ն գտնել b-ի և a-b-ի ամենամեծ ընդհանուր բաժանարարը գտնելով, մեծ a-ն նորից դիտարկելու փոխարեն։ Այս պրոցեսը կարող ենք կրկնել այնքան ժամանակ, քանի դեռ կամ a-ն, կամ b-ն կդառնան 0 (այդ դեպքում մեր ստացած թվիը կլինի ամենամեծ ընդհանուր բաժանարարը).
a, b = int(input()), int(input())
while a > 0 and b > 0:  # Եթե a == 0 կամ b == 0, ապա մյուսը նրանց ամենամեծ ընդհանուր բաժանարարն է
    if b > a:           # Փորձենք միշտ ապահովել a ≥ b պայմանը
        a, b = b, a     # Թվերը փոխենք իրենց տեղերով
    a, b = a - b, b     # (a, b)-ի ամենամեծ ընդհանուր բաժանարարը նույնն է, ինչ (a-b, b)-ի ամենամեծ ընդհանուր բաժանարարը

d = b if a == 0 else a  # եթե a==0, ուրեմն b-ն է ամենամեծ ընդհանուր բաժանարարը, եթե b==0, ուրեմն a-ն է ամենամեծ ընդհանուր բաժանարարը
print('gcd:', d)
Եկեք դիտարկենք ալգորիթմի աշխատանքի մի քանի օրինակ.
a = 8, b = 12
  1. Քանի որ b > a ⇒ փոխում ենք տեղերով ⇒ a = 12, b = 8 a = 12 - 8 = 4, b = 8
  1. Քանի որ b > a ⇒ փոխում ենք տեղերով ⇒ a = 8, b = 4 a = 8 - 4 = 4, b = 4
  1. a = 4 - 4 = 0, b = 4
  1. վերջ ⇒ GCD = 4
a = 54, b = 24
  1. a = 54 - 24 = 30, b = 24
  1. a = 30 - 24 = 6, b = 24
  1. Քանի որ b > a ⇒ փոխում ենք տեղերով ⇒ a = 24, b = 6 a = 24 - 6 = 18, b = 6
  1. a = 18 - 6 = 12, b = 6
  1. a = 12 - 6 = 6, b = 6
  1. a = 6 - 6 = 0, b = 6
  1. վերջ ⇒ GCD = 6
a = 17, b = 16
  1. a = 17 - 16 = 1, b = 16
  1. Քանի որ b > a ⇒ փոխում ենք տեղերով ⇒ a = 16, b = 1 a = 16 - 1 = 15, b = 1
  1. a = 14, b = 1
  1. a = 13, b = 1
  1. a = 12, b = 1
  1. …
  1. …
  1. a = 0, b = 1
  1. վերջ ⇒ GCD = 1

Մուտք

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

Ելք

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

Օրինակներ

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