首页 > 编程语言 > 详细

模板 - 数学 - 同余 - 扩展欧几里得算法/ExtendEuclideanAlgorithm

时间:2019-11-18 23:54:45      阅读:141      评论:0      收藏:0      [点我收藏+]

扩展欧几里得算法。
修复了溢出longlong的bug。在int128下也不容易进一步溢出了。求解模n意义下a的逆元,即求方程LCE2(a,1,n,x),结果放入x中,返回值指示是否有解。

ll gcd(ll a, ll b) {
    if(b == 0)
        return a;
    while(ll t = a % b)
        a = b, b = t;
    return b;
}

ll ex_gcd(ll a, ll b, ll& x, ll& y) {
    if(b == 0) {
        x = 1, y = 0;
        return a;
    }
    ll d = ex_gcd(b, a % b, x, y), t;
    t = x, x = y, y = t - a / b * y;
    return d;
}

//解线性同余方程 ax + by = c ,无解返回false
bool LCE1(ll a, ll b, ll c, ll &x0, ll &y0) {
    ll x, y, d = ex_gcd(a, b, x, y);
    if(c % d)
        return false;
    ll k = b / gcd(a, b);
    x0 = ((x % k) * (c / d % k) % k + k) % k;
    y0 = (c - a * x0) / b;
    //x0是x的最小非负整数解
    //x=x0+b*t,y=y0-a*t,是方程的所有解,对所有整数t成立
    return true;
}

//解线性同余方程 ax = b mod n ,无解返回false
//和方程 ax + ny = b 等价
bool LCE2(ll a, ll b, ll n, ll &x0) {
    ll x, y;
    if(LCE2(a, n, b, x, y)) {
        ll k = n / gcd(a, n);
        x0 = (x % k + k) % k;
        //x0是最小非负整数解
        //x=x0+k*t,是方程的所有解,对所有整数t成立
        return true;
    } else
        return false;
}

未修复的版本理论上会快一点常数,没必要。但是还是做个提醒:

//解线性同余方程 ax + by = c ,无解返回false
bool LCE1(ll a, ll b, ll c, ll &x0, ll &y0) {
    ll x, y, d = ex_gcd(a, b, x, y);
    if(c % d)
        return false;
    ll k = c / d;
    x0 = x * k;
    y0 = y * k;
    //x=x0+b*t,y=y0-a*t,是方程的所有解,对所有整数t成立
    return true;
}

模板 - 数学 - 同余 - 扩展欧几里得算法/ExtendEuclideanAlgorithm

原文:https://www.cnblogs.com/KisekiPurin2019/p/11886449.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!