Хоёр тооны хамгийн их ерөнхий хуваагчийг (GCD) үлдэгдлээр нь хэдхэн алхамд олдог Euclid-ийн алгоритм.

Basic LevelХугацаа: O(log min(a, b))Санах ой: O(1)
HackerRank дээр бодох

Эхлээд жижиг бодлого

a = 18, b = 12 хоёрын GCD-г олъё. 18 % 12 = 6 тул GCD(18, 12) = GCD(12, 6). Дараа нь 12 % 6 = 0 тул GCD(12, 6) = GCD(6, 0) = 6.

Хариу 6: 18 = 6 · 3, 12 = 6 · 2. Хоёрхон удаа хуваагаад оллоо.

Энгийн аргаас санаа руу

Энгийн арга: a, b хоёрын багаас эхлэн доош тоо бүрийг шалгаж, хоёуланг нь хуваадаг эхнийхийг нь олно. a, b нь 10⁹ орчим бол тэрбум шалгалт болно.

Euclid-ийн санаа: a-г b-д хуваахад r үлдэгдэл гарвал GCD(a, b) = GCD(b, r). Учир нь a, b хоёуланг нь хуваадаг тоо r-ийг ч хуваана (r = a − q · b), эсрэгээрээ ч мөн. Тоонууд маш хурдан багасч, b = 0 болоход a нь хариу.

Нэр томьёо ба тэмдэглэгээ

GCD
Хамгийн их ерөнхий хуваагч. a, b хоёуланг нь хуваадаг хамгийн их тоо.
a % b
a-г b-д хуваасан үлдэгдэл.
swap(a, b)
Хоёр хувьсагчийн утгыг солино. Дараагийн алхамд их нь урдаа байна.
LCM
Хамгийн бага ерөнхий хуваагдагч: a / GCD(a, b) * b.
#aba % b1
252
105
a = 252b = 105

252 ба 105 хоёуланг нь хуваадаг хамгийн их тоо хэд вэ? Үүнийг GCD (хамгийн их ерөнхий хуваагч) гэдэг.

Алхам 1 / 8
Хурд
  • Шинэ үлдэгдэл
  • Дараагийн a, b
  • Өмнөх алхам
  • GCD
Слайд 1 / 6

GCD гэж юу вэ?

12 ба 18 хоёуланг нь хуваадаг хамгийн их тоо бол 6. Үүнийг хамгийн их ерөнхий хуваагч буюу GCD гэдэг. Одоо 252 ба 105-ын GCD-г олъё.

gcd-euclid.cpp
#include <bits/stdc++.h>
using namespace std;
int a, b;
int main() {
cin >> a >> b;
while (b != 0) {
a %= b;
swap(a, b);
}
cout << a << '\n';
return 0;
}

Юунд хэрэгтэй вэ?

Хоёр тоог хоёуланг нь хуваадаг хамгийн их тоог хурдан олох. Бутархай хураах, LCM олоход хэрэглэнэ: LCM = a / GCD × b.

Яаж ажилладаг вэ?

1. a %= b: a-г b-д хуваагаад үлдэгдлийг нь a болгоно. 2. swap(a, b): хоёр тооны байрыг солино. GCD(a, b) = GCD(b, a % b) тул хариу өөрчлөгдөхгүй, харин тоонууд багасна. 3. b = 0 болтол давтана. 4. b = 0 болоход a нь хариу. Оролт: нэг мөрөнд a ба b.

Яагаад зөв, хэр хурдан бэ?

Алхам бүрт GCD өөрчлөгдөхгүй, харин b хатуу багасна. b сөрөг болж чадахгүй тул хэзээ нэгэн цагт 0 болно. GCD(a, 0) = a тул тэр үеийн a нь хариу.

Хоёр алхам тутамд их тоо дор хаяж хоёр дахин багасдаг. Тиймээс алхмын тоо O(log min(a, b)). 10⁹ хүртэлх тоонд 45 хүрэхгүй удаа хуваана. Хамгийн олон алхам Фибоначчийн дараалсан хоёр тоон дээр гардаг.

Түгээмэл алдаа

  • b = 0 үед a % b бодвол 0-д хуваах алдаа гарна. while (b != 0) нөхцөл үүнээс хамгаална.
  • LCM-ийг a * b / g гэж бодвол a * b нь int-ээс хэтэрнэ. Эхлээд хуваа: a / g * b, бас long long ашигла.
  • swap(a, b)-ийг мартвал a нь b-гээс бага болоод b хэзээ ч өөрчлөгдөхгүй тул loop дуусахгүй.
  • Сөрөг тоо: C++-д % сөрөг үлдэгдэл өгч болно. Эхлээд abs() ав.

Хязгаарын тохиолдол

  • b = 0: loop ажиллахгүй, хариу a.
  • a < b: эхний алхамд a % b = a, swap хийгээд байраа солино. Ганц илүү алхам.
  • a = b: эхний алхамд үлдэгдэл 0, хариу a.
  • Харилцан анхны тоо (жишээ нь 64, 35): хариу 1.

Өөрийгөө шалга

  1. GCD(252, 105) хэд вэ? Хэдэн удаа хуваах вэ?

    Хариу харах

    21. 3 удаа: 252 % 105 = 42, 105 % 42 = 21, 42 % 21 = 0.

  2. LCM(4, 6) хэд вэ?

    Хариу харах

    12. GCD нь 2, тэгэхээр 4 / 2 · 6 = 12.

  3. GCD(17, 0) хэд вэ?

    Хариу харах

    17. b = 0 тул loop ажиллахгүй.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.a = 89, b = 55 үед хүснэгтийн мөр бүрийг (a, b, a % b) бич. Хэдэн удаа хуваах вэ?

    Hint харах

    Үлдэгдэл бүр Фибоначчийн өмнөх тоо болохыг ажигла.

    Хариу ба тайлбар

    (89, 55, 34), (55, 34, 21), (34, 21, 13), (21, 13, 8), (13, 8, 5), (8, 5, 3), (5, 3, 2), (3, 2, 1), (2, 1, 0). 9 удаа хуваана, GCD = 1.

  2. 2.Кодыг recursive function болгож бич.

    Hint харах

    b == 0 бол base case.

    Хариу ба тайлбар

    int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }. Ганц мөр, swap хэрэггүй.

  3. 3.n тоо (n ≤ 10⁵) өгөгдсөн. Бүгдийнх нь GCD ба LCM-ийг ол (LCM нь long long-д багтана).

    Hint харах

    GCD(a, b, c) = GCD(GCD(a, b), c).

    Хариу ба тайлбар

    g-г a[0] гэж эхлүүлээд тоо бүрээр g = gcd(g, a[i]). LCM-ийг мөн адил: l = l / gcd(l, a[i]) * a[i], long long ашиглана.

Жишээ

Оролт

252 105

Гаралт

21

Одоо өөрөө бодоод үз

Бодлого

Хичээл

Энэ сэдвийн хичээл удахгүй нэмэгдэнэ.