clear

// ExtendedEuclidean

// 欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两个方面。
// 计算公式gcd(a,b) = gcd(b,a mod b)

a       = hex( 1997 )
b       = hex( 615 )
t       = call gcd( $a, $b )

// 扩展欧几里得算法（Extended Euclidean algorithm）是欧几里得算法的扩展。
// 已知整数a、b，必存在整数x、y使得ax + by = gcd(a,b).

// 扩展欧几里得可以求出：
// a·x + m·y = gcd(a, m)
// 如果 gcd(a,m)=1，则变成：
// a·x + m·y = 1
// 把右边的 1 看成 mod m 的等式：
// a·x ≡ 1 (mod m)
// 所以 x 就是逆元

a       = hex( 10 )
m       = hex( 17 )
flag    = ""

x       = call modinv( $a, $m, &flag )
if $flag == 00
    tmp = big_mul( $a, $x )
    tmp = big_mod( $tmp, $m )
else
    tmp = big_mul( $m, $x )
    tmp = big_mod( $tmp, $a )
endif
if $tmp != 01
    ? "求逆失败"
    pause
endif

m       = hex( 10 )
a       = hex( 17 )
flag    = ""

x       = call modinv( $a, $m, &flag )
if $flag == 00
    tmp = big_mul( $a, $x )
    tmp = big_mod( $tmp, $m )
else
    tmp = big_mul( $m, $x )
    tmp = big_mod( $tmp, $a )
endif
if $tmp != 01
    ? "求逆失败"
    pause
endif



a       = int2hex( 0987654321012345678909876543210123456789 )
m       = int2hex( 1000000000000000000000000000000000000037 )

x       = call modinv( $a, $m, &flag )
if $flag == 00
    tmp = big_mul( $a, $x )
    tmp = big_mod( $tmp, $m )
else
    tmp = big_mul( $m, $x )
    tmp = big_mod( $tmp, $a )
endif
if $tmp != 01
    ? "求逆失败"
    pause
endif

a       = int2hex( 0314159265358979323846264338327950288419 )
m       = int2hex( 0271828182845904523536028747135266249775 )

x       = call modinv( $a, $m, &flag )
if $flag == 00
    tmp = big_mul( $a, $x )
    tmp = big_mod( $tmp, $m )
else
    tmp = big_mul( $m, $x )
    tmp = big_mod( $tmp, $a )
endif
if $tmp != 01
    ? "求逆失败"
    pause
endif


end

gcd:
    prompt off
    local a = getpara
    local b = getpara
    local tmp
    local r

    if $a < $b
        tmp = $a
        a   = $b
        b   = $tmp
    endif

    r       = big_mod( $a, $b )
    if $r == 00
        r   = $b
    else
        r   = call gcd( $b, $r )
    endif
    prompt on
return $r

ExtEuclid:
    prompt off
    local a         = getpara
    local b         = getpara
    local x_abs     = getpara
    local x_sign    = getpara
    local y_abs     = getpara
    local y_sign    = getpara

    local x
    local g
    local tmp


    if $b == 00
        x       = set_value( $x_abs, 01 )
        x       = set_value( $x_sign, 01 )
        x       = set_value( $y_abs, 00 )
        x       = set_value( $y_sign, 01 )
        g       = $a
    else
        local x1_abs
        local y1_abs
        local x1_sign
        local y1_sign
        tmp     = big_mod( $a, $b )
        g       = call exteuclid( $b, $tmp, &x1_abs, &x1_sign, &y1_abs, &y1_sign )

        x       = set_value( $x_abs, $y1_abs )
        x       = set_value( $x_sign, $y1_sign )

        local k
        local t_abs
        local t_sign
        local bigA
        local bigAS
        local bigB
        local bigBS

        k       = big_div( $a, $b )
        t_abs   = big_mul( $y1_abs, $k )
        t_sign  = $y1_sign


        bigA    = $x1_abs
        bigAS   = $x1_sign

        bigB    = $t_abs
        bigBS   = $t_sign
        if $bigbs == 01
            bigbs   = 00
        else
            bigbs   = 01
        endif

        if $bigas == $bigbs
            tmp = big_add( $biga, $bigb )
            x   = setvalue( $y_abs, $tmp )
            x   = setvalue( $y_sign, $bigas )
        else
            if $biga >= $bigb
                tmp = big_sub( $biga, $bigb )
                x   = setvalue( $y_abs, $tmp )
                x   = setvalue( $y_sign, $bigas )
            else
                tmp = big_sub( $bigb, $biga )
                x   = setvalue( $y_abs, $tmp )
                x   = setvalue( $y_sign, $bigbs )
            endif
        endif
    endif
    prompt on
return $g

// long long ModInv(long long a, long long m)
// {
//     long long x_abs, y_abs;
//     int       x_sign, y_sign;

//     long long g = ExtEuclid(a, m,
//                             &x_abs, &x_sign,
//                             &y_abs, &y_sign);

//     if (g != 1)
//         return -1;   /* 不存在逆元 */

//     /* 还原 x，但这是最终一步，允许一次负数 */
//     if (x_sign < 0)
//         x_abs = m - (x_abs % m);

//     return x_abs % m;
// }
ModInv:
    prompt off
    local a         = getpara
    local m         = getpara
    local swap_flag = getpara


    local x_abs
    local y_abs
    local x_sign
    local y_sign

    local g

    local res
    local tmp

    // 检查是否经过数据交易，要求a < m
    if $a > $m
        tmp = $a
        a   = $m
        m   = $tmp
        g   = setvalue( $swap_flag, 01 )
    else
        g   = setvalue( $swap_flag, 00 )
    endif

    g               = call exteuclid( $a, $m, &x_abs, &x_sign, &y_abs, &y_sign )
    if $g != 01
        res = 00
    else
        if $x_sign == 00        // 负数
            tmp     = big_mod( $x_abs, $m )
            x_abs   = big_sub( $m, $tmp )
        endif
    endif

    res             = big_mod( $x_abs, $m )
    prompt on
return $res