'Subject: Minimal solution of the Diophantine equation ax - by = c.
'         The equation is solvable only if gcd(a, b) divides c,
'         input c = 0 calculates ax - by = gcd(a, b).
'Author : Sjoerd.J.Schaper
'Date   : 21-12-2003
'Code   : QuickBasic, PDS, VBdos
REM $LANG: "qb"
REM $INCLUDE: 'largeint.bi'
CONST a = 0, b = 1, c = 2
CONST a1 = 3, b1 = 4, d = 5
r = LargeInit(d, "exteucli")
CLS : tim# = TIMER: lin = 8

begin:
LOCATE 1, 1
PRINT "   +---------------------------------+"
PRINT "   |  input                          |"
PRINT "   |  a, b, c to solve ax - by = c,  |"
PRINT "   |  a = 0 to exit.                 |"
PRINT "   |                                 |"
PRINT "   +---------------------------------+"
LOCATE 5, 7: INPUT ; "a"; ai$
IF INSTR(ai$, "'") THEN GOTO begin
IF VAL(ai$) = 0 THEN GOTO eind
INPUT ; " b"; bi$: INPUT " c"; ci$
IF VAL(bi$) = 0 THEN GOTO begin

LOCATE lin, 1
Readst a, ai$
Printn a, "   a = ", "", 2
Readst b, bi$
Printn b, "   b = ", "", 2
Readst c, ci$: r = Isf(c, 0)
IF r THEN
   Prints "   c = (a,b)", 1
ELSE
   Printn c, "   c = ", "", 2
END IF

Dup a, a1
Dup b, b1: Chs b1
Bezout a1, b1, d
Printn d, "(a,b)= ", "", 2

s = Cmp(c, d) = 0: Sw = -1
IF NOT (r OR s) THEN
   Printn a1, "a^-1 = ", "", 2
   Printn b1, "b^-1 = ", "", 2
   IF NOT Isf(d, 1) THEN '         gcd(a,b) > 1
      Ldiv a, d: Ldiv b, d
      Divd c, d, t0: Swp c, t0
      Sw = Isf(t0, 0)
   END IF
   IF Sw THEN
      Lmul b1, c '                     b^ -1 * c
      Divd b1, a, t0 '             y =           Mod a
      Mult b, b1, t0: Add t0, c '      b * y + c
      Divd t0, a, a1 '             x =           / a
   END IF
END IF

IF Sw THEN
   Printn a1, "   x = ", "", 2
   Printn b1, "   y = ", "", 2
ELSE
   Prints "illegal parameter c", 1
END IF
Prints "", 1
lin = CSRLIN
GOTO begin

eind:
LOCATE lin, 1
g$ = STR$(CSNG(TIMER - tim#))
Prints "Timer:" + g$ + " s", 1
CALL Term
SYSTEM

