| [Posjetilac (113.218.*.*)]odgovori [Kineski ] | Vrijeme :2024-06-24 | Proširi Euklidski algoritam
Prošireni euklidski algoritam, ili skraćeno EXGCD, općenito se koristi za rješavanje neodređenih jednadžbi, jednadžbi linearne kongruencije, inverznih elemenata modula i tako dalje
Lemma: Prisutnost x , y je takva da je gcd(a,b)=ax by
Dokazati:
Kada je b=0, gcd(a,b)=a, u kojoj točki x=1, y=0
Kada je b!=0,
Neka ax1 by1=gcd(a,b)=gcd(b,a%b)=bx2 (a%b)y2
i zato što je a%b=a-a/b*b
Zatim ax1 by1=bx2 (a-a/b*b)y2
ax1 by1=bx2 ay2-a/b*by2
ax1 by1=ay2 bx2-b*a/b*y2
ax1 by1=ay2 b(x2-a/b*y2)
Otopina daje x1=y2 , y1=x2-a/b*y2
Jer kad je b=0 postoji x, y je posljednji skup rješenja
Otopina za svaku skupinu može se dobiti iz potonje skupine
Dakle, rješenje prve skupine x , y mora postojati
Dokazali
Na temelju gore navedenog dokaza koriste se rekurzivne prakse pri provedbi
Rekurzivno prijeđite na sljedeći sloj, a vratite x=1 i y=0 kada se dostigne posljednji sloj, a to je b=0
Zatim prema x=y' , y=x'-a/b/y' ( x' i y' su x i y sljedećeg sloja ) kako bi se dobila otopina trenutnog sloja
Kontinuirano izračunavajte otopinu trenutnog sloja i vratite se, a na kraju se vratite na prvi sloj kako biste dobili izvornu otopinu |
|
