求解同余方程组（难度：2颗星）

深藏阁楼爱情的钟 2022-06-15 12:21 363阅读 0赞

问题描述：

有一个同余方程组，有N个同余方程组成（N由用户输入），另外每个同余方程的a\[i\]和m\[i\]也又用户指定，如下所示：

x≡a\[1\](mod m\[1\])  
x≡a\[2\](mod m\[2\])  
x≡a\[3\](mod m\[3\])  
x≡a\[4\](mod m\[4\])  
…  
x≡a\[n\](mod m\[n\])

求x的最小正整数解。

问题分析：

参考我的另外一篇文章“中国剩余定理”  
[http://blog.csdn.net/yi\_ming\_he/article/details/72848318][http_blog.csdn.net_yi_ming_he_article_details_72848318]

参考代码：

#include <stdio.h>
    
    typedef __int64 int64;
    int n, a[100], m[100];//m[100]是mod数组
    
    int64 ExtendGcd(int64 a, int64 b, int64* px, int64* py)
    {
        int64 nRet, temp;
        if (b == 0)
        {
            if (px && py)
            {
                *px = 1;
                *py = 0;
            }
            return a;
        }
    
        nRet = ExtendGcd(b, a % b, px, py);
        if (px && py)
        {
            temp = *px;
            *px = *py;
            *py = temp - a / b * (*py);
        }
        return nRet;
    }
    
    int64 ChinaRemainder()
    {
       //中国剩余定理只适合解决m数组两两互质的情况
        int64 M = 1, res = 0, x, y, tempM;
        int i;
        for (i = 0; i < n; i++)
            M *= m[i];
    
        for (i = 0; i < n; i++)
        {
            tempM = M / m[i];
            ExtendGcd(tempM, m[i], &x, &y);
            res = (res + tempM * x * a[i]) % M;
        }
        res = (res + M) % M;
        return res;
    }
    
    int main()
    {
        scanf_s("%d", &n);//同余方程组的方程个数
        int i;
        for (i = 0; i < n; i++)
            scanf_s("%d%d", &a[i], &m[i]);
    
        printf("%I64d\n", ChinaRemainder());
        return 0;
    }

运行结果：

![这里写图片描述][SouthEast]

[http_blog.csdn.net_yi_ming_he_article_details_72848318]: http://blog.csdn.net/yi_ming_he/article/details/72848318
[SouthEast]: /images/20220615/a84043e8fe02456fba1fc99c82404f79.png