中国剩余定理及同余方程解法（这里同余方程属于一种情况，剩余定理属于一种解法）

朴灿烈づ我的快乐病毒、 2024-04-18 19:04 60阅读 0赞

> 中国剩余定理又叫孙子定理即：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。即可以得到下方程
> 
> ![format_png][]
> 
> 中间有个三个横的类似于等于符号，“ ≡ ” 这个符号叫做同余，上面的方程也叫同余方程
> 
> 同余是什么？字面意思理解：同一个余数，
> 
> 即：假设有a b c(假设a>b)三个正整数 假如a对c取模得到的数与b对c取模得到的数相同即可以得出结论a≡bmodc
> 
> 也可以理解为(a-b)能整除c
> 
> a和b关于模c同余
> 
> 例如：37≡23mod7  这里37%7=2 23%7=2  同时（37-23)%7=0 所以可以看出37 和23关于模7同余
> 
> 性质：
> 
> 1.[反身][Link 1]性：a≡a (mod m)；
> 
> 2.[对称][Link 2]性：若a≡b(mod m)，则b≡a (mod m)；
> 
> 3.传递性：若a≡b(mod m)，b≡c(mod m)，则a≡c(mod m)；
> 
> 4.同余式相加：若a≡b(mod m)，c≡d(mod m)，则a(+-)c≡b(+-)d(mod m)；
> 
> 5.同余式相乘：若a≡b(mod m)，c≡d(mod m)，则ac≡bd(mod m)。
> 
> **证明：**
> 
> ∵a≡b(mod m)∴m|(a-b) 同理m|(b-c),
> 
> ∴m|\[(a-b)+(b-c)\]∴m|(a-c).
> 
> 故a≡c(mod m*).*
> 
> 6.[线性运算][Link 3]：如果a ≡ b (mod m)，c ≡ d (mod m)，那么
> 
> (1)a ± c ≡ b ± d (mod m)；
> 
> (2)a \* c ≡ b \* d (mod m)。
> 
> **证明：**
> 
> (1)∵a≡b(mod m),
> 
> ∴m|(a-b)
> 
> 同理 m|(c-d)
> 
> ∴m|\[(a-b)±(c-d)\]
> 
> ∴m|\[(a±c)-(b±d)\]
> 
> ∴a ± c ≡ b ± d (mod m)
> 
> (2)∵ac-bd=ac-bc+bc-bd=c(a-b)+b(c-d)
> 
> 又 m|(a-b) , m|(c-d)
> 
> ∴m|(ac-bd)
> 
> ∴a \* c ≡ b \* d (mod m)
> 
> 7.[除法][Link 4]：若![format_png 1][]，则![format_png 2][],其中gcd(c,m)表示c和m的[最大公约数][Link 5]，特殊地，![format_png 3][]
> 
>  则![format_png 4][]；
> 
> 8.[幂运算][Link 6]：如果![format_png 5][]，那么![format_png 6][] ；
> 
> 9.若![format_png 5][] ,n=m，则![format_png 7][] ；
> 
> 10.若![format_png 8][] ，(i=1,2...n) 则![format_png 9][] ，其中![format_png 10][] 表示m1,m2,...mn的[最小公倍数][Link 7]。

>  剩余定理解法代码：

ll exgcd(ll a,ll b,ll &x,ll &y)///扩展欧几里得
    {
        if(a==0&&b==0)
            return -1;
        if(b==0)
        {
            x=1;
            y=0;
            return a;
        }
        ll d=exgcd(b,a%b,y,x);
        y-=a/b*x;
        return d;
    }
    /*
    同余方程书写的原理：
    x=a0*x0+b0
    x=a1*x1+b1
    ……
    x=an*x+bn
    两两连立得到二元一次方程组
    a0*x0-a1*x1=b1-b0
    然后再用扩展欧几里得求解
    最终得到的结果a1为最终余数
    即为n1*k+a1
    因为大部分要求最小的所以设k为0然后直接返回a1即可
    */
    ll a[maxn],b[maxn];///数组a为除数数组b为余数
    ll excrt()///同余方程解法
    {
        ll a1=b[0],n1=a[0],a2,n2,d,x,y,gcd;
        for(int i=1; i<n; i++)
        {
            a2=b[i];
            n2=a[i];
            d=a2-a1;
            gcd=exgcd(n1,n2,x,y);
            if(d%gcd)
                return -1;
            x=((x*d/gcd)%(n2/gcd)+(n2/gcd))%(n2/gcd);
            a1=x*n1+a1;
            n1=n1*n2/gcd;
        }
        return a1;
    }

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MyLmJkc3RhdGljLmNvbS8tZm8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcGljL2l0ZW0vODBjYjM5ZGJiNmZkNTI2NmRlN2NjMjMxYTgxODk3MmJkNDA3MzZiYi5qcGc?x-oss-process=image/format,png
[Link 1]: https://baike.baidu.com/item/%E5%8F%8D%E8%BA%AB
[Link 2]: https://baike.baidu.com/item/%E5%AF%B9%E7%A7%B0
[Link 3]: https://baike.baidu.com/item/%E7%BA%BF%E6%80%A7%E8%BF%90%E7%AE%97
[Link 4]: https://baike.baidu.com/item/%E9%99%A4%E6%B3%95
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MyLmJkc3RhdGljLmNvbS8tZm8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcyUzRDE0NS9zaWduPWNkODRiZTFhMjVkZGEzY2MwZmU0YmMyNDM0ZTgzOTA1LzQ4NTQwOTIzZGQ1NDU2NGUxNGVhYzNiY2I4ZGU5YzgyZDA1ODRmYTMuanBn?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MzLmJkc3RhdGljLmNvbS83UG8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcyUzRDE2MC9zaWduPTRjYjZlODU4YTA2NDAzNGYwYmNkYzYwMDlmYzI3OTgwLzAzMDg3YmY0MGFkMTYyZDlmNTllNDQ5OTFhZGZhOWVjOGIxM2NkYzYuanBn?x-oss-process=image/format,png
[Link 5]: https://baike.baidu.com/item/%E6%9C%80%E5%A4%A7%E5%85%AC%E7%BA%A6%E6%95%B0
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MxLmJkc3RhdGljLmNvbS8tdm8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcyUzRDg5L3NpZ249ZWYwNTNlNDBlYmZlOTkyNWNmMGM2NDU5MzVhODMxOWIvNWJhZmE0MGY0YmZiZmJlZDdlNDgxMGZhNzNmMGY3MzZhZmMzMWYyNS5qcGc?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MwLmJkc3RhdGljLmNvbS8tNG8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcyUzRDkwL3NpZ249ZGZlMDk2M2VhZDFlYThkMzhlMjI3ODA0OTYwYTE4ZmUvMzgxMmIzMWJiMDUxZjgxOTZhMDIyMmNmZDFiNDRhZWQyZTczZTcxNC5qcGc?x-oss-process=image/format,png
[Link 6]: https://baike.baidu.com/item/%E5%B9%82%E8%BF%90%E7%AE%97
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MwLmJkc3RhdGljLmNvbS8tNG8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcyUzRDkwL3NpZ249MTRjZGQ5MzU2ZTM4MGNkN2UyMWVhZWVkYTA0NGMxMTUvNzFjZjNiYzc5ZjNkZjhkYzc1YjNhOTE0YzYxMTcyOGI0NjEwMjhhYy5qcGc?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MyLmJkc3RhdGljLmNvbS8tZm8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcyUzRDEwNi9zaWduPTMxYzNlNzZiYmY4ZjhjNTRlN2QzYzEyZjBjMjgyZGVlL2E2ODZjOTE3N2YzZTY3MDk1N2FmNjQ3YTMwYzc5ZjNkZjlkYzU1ODMuanBn?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MwLmJkc3RhdGljLmNvbS8tNG8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcyUzRDg2L3NpZ249ZTQwYTY2YmIwN2YzZDdjYTA4ZjYzMjcwZjMxZmU5OTIvZTFmZTk5MjViYzMxNWM2MDQ4ODA0YTZhODZiMWNiMTM0OTU0NzcxOS5qcGc?x-oss-process=image/format,png
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MxLmJkc3RhdGljLmNvbS85dm8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcyUzRDk2L3NpZ249YmIxNmQ5YTQ3OThiNDcxMGNhMmZmMWNhYzJjZTYzMWMvYTgwMTRjMDg2ZTA2MWQ5NTBiY2MxNmJkNzBmNDBhZDE2M2Q5Y2FhOC5qcGc?x-oss-process=image/format,png
[format_png 9]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MyLmJkc3RhdGljLmNvbS8tZm8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcyUzRDE4Mi9zaWduPTUwYWU4OGEzZjZmYWFmNTE4MGUzODViN2JlNTU5NGVkL2M4MTc3ZjNlNjcwOWM5M2RlZTdhMmU3Mjk0M2RmOGRjZDAwMDU0YWUuanBn?x-oss-process=image/format,png
[format_png 10]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9nc3MxLmJkc3RhdGljLmNvbS8tdm8zZFNhZ194STRraEdrcG9XSzFIRjZoaHkvYmFpa2UvcyUzRDEwMi9zaWduPWIyODU3MmJjYzIzZDcwY2Y0OGZhYWUwZGNhZGRkMWJhL2M5OTVkMTQzYWQ0YmQxMTNiZTRiOTdiNzUxYWZhNDBmNGFmYjA1YjQuanBn?x-oss-process=image/format,png
[Link 7]: https://baike.baidu.com/item/%E6%9C%80%E5%B0%8F%E5%85%AC%E5%80%8D%E6%95%B0