Problem I. 124. (February 2006)
I. 124. Write a program to solve Diophantine equations of the form ax+by=c. The program receives the integers a, b and c having at most four digits in one line from the standard input, separated by spaces. Your program should display the integer solutions in a parametric form in one line as shown below. If there is no solution, print the text ,,no solution''.
Examples:
The source code (i124.pas, i124.cpp, ...) is to be submitted.
(10 pont)
Deadline expired on March 16, 2006.
Sorry, the solution is available only in Hungarian. Google translation
A feladat megoldásához először nézzük végig a speciális eseteket, majd az általános esetet.
1. eset: 0*x+0*y=0
Ha a és b is 0, akkor az egyenletnek csak akkor van megoldása, ha c is 0. Ebben az egyetlen esetben van szükségünk két változóra a megoldáshoz:
x=t; y=u
2. eset: 0*x+b*y=c
Ha a vagy b 0, akkor az egyenlet csak akkor oldható meg, ha a nem-nulla szorzótényező osztója c-nek, lenkező esetben az egyenlet bal oldala osztható lenne b-vel, a jobb oldala viszont nem. Ebben az esetben a megoldás:
x=t; y=c/b
3. eset: a*x+b*y=c
Ha sem a, sem b nem 0, a megoldás a kétváltozós, lineáris diophantoszi egyenlet általános megoldása:
x=x0+b/lnko(a,b)*t; y=y0; a/lnko(a,b)*t
ahol x0 és y0 az egyenlet egy megoldása. Megoldás csak akkor létezik, ha c osztható lnko(a,b)-vel. (lnko(a,b) = a és b legnagyobb közös osztója )
x0 és y0 meghatározására létenek különböző algoritmusok, de mivel az együtthatók viszonylag kicsi számok, a legegyszerübb, ha sorban végignézzük 0-tól az egész számokat, míg találunk egy megfelelőt: c-a*x0 -nak oszthatónak kell lennie b-vel. Bizotsan találunk egy ilyet, a [0;b/lnko(a,b)] halmazban.
A megoldáshoz szükségünk van az lnko(a,b) meghatározására, ezt az euklideszi algoritmussal könnyen megtehetjük: vegyük a nagyobbik szám helyett a nagyobbik szám kisebbik számmal való osztási maradékát, és ezt ismételjük addig, amíg valamelyik szám 0 nem lesz.
(x0 és y0 meghatározására lehetséges lenne például úgy, hogy az egyenletet átalakítjuk: (tegyük föl, hogy a<b, és jelölje b%a a b a-val való osztási maradékát, b/a pedig b és a hányadosának egészrészét)
c=b*y+a*x=(b/a*a+b%a)*y+a*x=a*(b/a*y+x)+b%a*y=a*z+b%a*y=...
ez az átalakítás az euklideszi algoritmus szerint megy, minden lépésben egy új ismeretlent bevezetve. Az átalakítások végén:
c=lnko(a,b)*xn+0*xn-1
egyenletet kapjuk, innen xn értéke meghatározható. xn-1 értékét pedig szabadon megválaszthatjuk. Ebből az egyenletből az is látszik, hogy miért kell c-nek oszthatónak lennie lnko(a,b)-vel. xn és xn-1-ből visszaszámolható x és y, ami a diophantoszi egyenlet egy megoldása lesz.)
Letölthető megoldás: i124.pas
Engedy István
Statistics:
10 students sent a solution. 10 points: Balambér Dávid, Czigler András, Györök Péter, Kovács 129 Péter, Ozsvárt László, Szoldatics András, Véges Márton, Vincze János. 3 points: 1 student. 0 point: 1 student.
Problems in Information Technology of KöMaL, February 2006