二元一次不定方程的大衍求一术解法的VB源码

二元一次不定方程的大衍求一术解法的VB源码

 

 

    我们清楚，二元一次不定方程可用欧几里德扩展算法，或者同余方程的欧拉解法，以及中国传统的方法大衍求一术来解。同余方程的欧拉解法程序算法复杂，且需经递归。而欧几里德扩展算法如果不递归，则也需要进行回退求解。所以，只有大衍求一术才是最简单的算法。这是08年就写出的老代码了，VB6的源码。从本人其它博客现搬到iteye.com网站,分享给更多的人。以下是VB程序的源码。

Option Explicit

'visual basic source code for finding x, y such that linear diophantine equation
'Copyright: 2008 Bardo QI

Function gcd(ByVal a As Long, ByVal b As Long)
    'get great common division
    Dim c As Long, tmp As Long
   
    If (a < b) Then
        tmp = a
        a = b
        b = tmp
    End If

    Do While (b <> 0)
        c = b
        b = a Mod b
        a = c
    Loop
    gcd = a

End Function

Function gma(ByVal g As Long, ByVal m As Long) As Long
    'get special solution for linear diophantine: ax+by=1
    Dim LT As Long, RT As Long, LD As Long, RD As Long
    Dim tmp As Long, x As Long
   
    If Abs(g) > Abs(m) Then
        g = g Mod m
    End If
   
    LT = 1: LD = 0: RT = g: RD = m
    x = 0

    Do While (RT <> 1)
        x = RD \ RT
        RD = RD Mod RT
        LD = x * LT + LD
       
        x = RT \ RD
        If RD = 1 Then
            LT = (x - 1) * LD + LT
            RT = 1
            Exit Do
        Else
            RT = RT Mod RD
        End If
        LT = x * LD + LT
    Loop
    gma = LT
   
End Function

Function Diophantine(ByVal a As Long, ByVal b As Long, ByVal c As Long, _
                    x As Long, y As Long, ar As Long, br As Long) As Boolean
    'Find the x,y such that a*x + b*y = k*gcd(a,b)
    Dim g As Long, tmp As Long, x0 As Long, y0 As Long
    Dim am As Long, bm As Long, t As Long
   
    g = gcd(Abs(a), Abs(b))
    If (c Mod g <> 0) Then
        Diophantine = False: Exit Function
    End If
    If a < 0 Then
        a = -a: b = -b: c = -c
    End If
    br = a / g: ar = b / g
    am = br: bm = ar
    If ar > br Then
        bm = ar Mod br
    End If
    If am > bm Then
        y0 = gma(Abs(bm), Abs(am))
    Else
        y0 = 1
    End If
    If (b < 0) Then
        y0 = -y0
    End If
    x0 = (1 - ar * y0) / br
    x = c * x0 / g: y = c * y0 / g
    'let y to mininized value
    t = y \ br
    y = y Mod br
    x = x + ar * t
   
    ar = -ar
   
    Diophantine = True
   
End Function