Хамгийн их ерөнхий хуваагч буюу GCD-г олохын зэрэгцээ x × a + y × b = GCD байх бүхэл x, y-г олдог арга. Euclid-ийн алгоритмын өргөтгөл.

IntermediateХугацаа: O(log min(a, b))Санах ой: O(1)

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

a = 30, b = 12 байг. Хамгийн их ерөнхий хуваагч буюу GCD нь 6. Харин 30 · x + 12 · y = 6 байх бүхэл x, y олж чадах уу?

Хүснэгтээр бодъё. Мөр бүрт r, x, y байна: (30, 1, 0), (12, 0, 1). q = 2 тул дараагийн мөр нь (6, 1, −2). Дахиад q = 2 болоход (0, −2, 5) гарч зогсоно. Хариу: GCD = 6, x = 1, y = −2. Шалгая: 30 − 24 = 6.

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

Энгийн арга бол x, y-г бүх утгаар туршиж үзэх. Хариу хаана байгааг мэдэхгүй тул энэ нь эцэс төгсгөлгүй хайлт болно.

Euclid-ийн алгоритм a-г b-д хувааж, үлдэгдлээр нь солисоор GCD-д хүрдэг. Үлдэгдэл бүр нь a, b-гийн бүхэл коэффициенттэй нийлбэр. Тиймээс тоо бүрийн хажууд түүний "жор" болох x, y-г хадгалж явбал GCD-д хүрэхэд түүний жор бэлэн байна.

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

GCD
Хамгийн их ерөнхий хуваагч. C++-д __gcd(a, b) эсвэл gcd(a, b).
q
a / b: a-д b хэдэн удаа багтахыг заана.
(a, x, y), (b, nx, ny)
Хүснэгтийн сүүлийн хоёр мөр. Үргэлж a = x · A + y · B ба b = nx · A + ny · B байна.
Bézout-гийн тэгшитгэл
A · x + B · y = GCD(A, B). Бүхэл шийд үргэлж оршин байдаг.
#rqxy0
240
1
0
1
46
0
1
a = 240b = 46x = 1y = 0nx = 0ny = 1

240 ба 46 хоёрын хамгийн их ерөнхий хуваагч буюу GCD-г олохын зэрэгцээ x × 240 + y × 46 = GCD байх x, y-г хайна. Мөр бүрт r = x × 240 + y × 46 байхаар хөтөлнө. Эхний хоёр мөр амархан: 240 = 1 × 240 + 0 × 46, 46 = 0 × 240 + 1 × 46.

Алхам 1 / 22
Хурд
  • Ашиглаж буй мөр
  • Сая бодсон
  • Хэрэггүй болсон мөр
  • Хариу
Слайд 1 / 6

GCD дээр нэмэлт бэлэг

Хамгийн их ерөнхий хуваагч буюу GCD(240, 46) = 2 гэдгийг мэднэ. Харин 240 × x + 46 × y = 2 байх бүхэл x, y-г олж чадах уу? Extended Euclid үүнийг GCD бодох зуураа олчихдог.

extended-euclid.cpp
#include <bits/stdc++.h>
using namespace std;
long long a, b, x, y, nx, ny, q;
int main() {
cin >> a >> b;
x = 1, y = 0, nx = 0, ny = 1;
while (b != 0) {
q = a / b;
tie(a, b) = make_pair(b, a - q * b);
tie(x, nx) = make_pair(nx, x - q * nx);
tie(y, ny) = make_pair(ny, y - q * ny);
}
cout << a << ' ' << x << ' ' << y << '\n';
return 0;
}

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

a × x + b × y = c тэгшитгэлийн бүхэл шийдийг олно. m анхны биш үед ч mod дахь урвуу тоог олж чадна.

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

1. Хүснэгтийн мөр бүрт r, x, y байна: r = x × a + y × b. Эхний хоёр мөр нь (a, 1, 0) ба (b, 0, 1). 2. q = a / b: a-д b хэдэн удаа багтахыг олно. 3. Шинэ мөр = дээрх мөр − q × доорх мөр. r, x, y гурван баганыг адилхан хасна. 4. b = 0 болтол давтана. Сүүлийн 0 биш мөр нь хариу: GCD, x, y. Оролт: a, b. GCD, x, y-г хэвлэнэ.

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

Эхний хоёр мөр шууд зөв: A = 1 · A + 0 · B, B = 0 · A + 1 · B. Шинэ мөрийг "дээрх мөр − q × доорх мөр" гэж гаргадаг. r, x, y гурвыг адилхан хасдаг тул r = x · A + y · B тэнцэл шинэ мөрөнд ч хадгалагдана. Үлдэгдэл 0 болоход өмнөх мөрийн r нь GCD бөгөөд түүний x, y нь хариу.

Алхмын тоо энгийн Euclid-тэй ижил: O(log min(A, B)). Хамгийн муу тохиолдол нь Фибоначчийн дараалсан хоёр тоо. 10⁹ хүртэлх тоонд ч 45-аас хэтрэхгүй алхам.

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

  • x, y-г зөвхөн эерэг гэж бодох. 240, 46 дээр x = −9 гарна. Эерэг x хэрэгтэй бол (x % m + m) % m гэж засна.
  • Мөр шинэчлэхэд хуучин утгыг дарчихах. x = nx; nx = x - q * nx; гэж бичвэл буруу. tie(x, nx) = make_tuple(nx, x - q * nx) эсвэл түр хувьсагч ашигла.
  • Том тоон дээр q * nx int-ээс хэтрэх. 10⁹ орчим тоонд long long ашигла.

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

  • b = 0: loop ажиллахгүй, хариу нь GCD = a, x = 1, y = 0.
  • a < b: эхний алхамд q = 0 болж, хоёр мөр байраа сольчихно. Дараа нь ердийнхөөрөө үргэлжилнэ.
  • a нь b-д хуваагдана: нэг алхамд үлдэгдэл 0 болж, GCD = b гарна.

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

  1. a = 7, b = 0 бол хариу юу вэ?

    Хариу харах

    GCD = 7, x = 1, y = 0.

  2. a = 35, b = 12 бол хариу юу вэ?

    Хариу харах

    GCD = 1, x = −1, y = 3. Шалгая: −35 + 36 = 1.

  3. Дээрх хариунаас 12-ын mod 35 дахь урвуу тоо хэд вэ?

    Хариу харах

    3. 12 · 3 = 36, 36-г 35-д хуваахад үлдэгдэл 1.

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

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

  1. 1.a = 99, b = 78 дээр хүснэгтийг гараар бөглөж GCD, x, y-г ол.

    Hint харах

    q-ууд нь 1, 3, 1, 2, 2 гарна.

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

    GCD = 3, x = −11, y = 14. Шалгая: −1089 + 1092 = 3.

  2. 2.a · x + b · y = c тэгшитгэлийн бүхэл шийдийг ол, эсвэл шийдгүй гэж хэвлэ.

    Hint харах

    c нь GCD-д хуваагдах ёстой.

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

    g = GCD гэе. c % g != 0 бол шийдгүй. Үгүй бол олсон x, y-г хоёуланг нь c / g-гээр үржүүлнэ.

  3. 3.m анхны биш үед a-гийн mod m дахь урвуу тоог ол. Жишээ нь a = 12, m = 35.

    Hint харах

    12 · x + 35 · y = 1 гэж бичээд x-ийг ол.

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

    Extended Euclid-ээр GCD = 1, x = 3 гарна. GCD ≠ 1 бол урвуу тоо байхгүй. x сөрөг гарвал (x % m + m) % m.

Жишээ

Оролт

240 46

Гаралт

2 -9 47