用C语言编程实现计算同余式组x≡b1(mod m1),x≡≡b2(mod m2)的解

#include <stdio.h>

int main()
{
int b1, m1, b2, m2;
printf("请输入同余式组x≡b1(mod m1),x≡b2(mod m2)的参数：\n");
printf("b1 = ");
scanf("%d", &b1);
printf("m1 = ");
scanf("%d", &m1);
printf("b2 = ");
scanf("%d", &b2);
printf("m2 = ");
scanf("%d", &m2);

int M1 = m1, M2 = m2;
int y1 = 1, y2 = 0;
while (m1 != 1)
{
int q = m1 / m2;
int t = m2;
m2 = m1 % m2;
m1 = t;
t = y2;
y2 = y1 - q * y2;
y1 = t;
}
if (y1 < 0)
y1 += M1;

int x = (b1 * M2 * y2 + b2 * M1 * y1) % (M1 * M2);
printf("同余式组的解为：x ≡ %d (mod %d)\n", x, M1 * M2);

return 0;
}

相关问题

用c语言编程实现计算同余式组x≡b1(mod m1) x≡b2(mod m2) 的解

#include <stdio.h>

int main()
{
int b1, m1, b2, m2; // 输入的同余式组参数
int M1, M2, y1, y2, x; // 中间变量
printf("输入同余式组：x≡b1(mod m1) x≡b2(mod m2)\n");
printf("请输入b1和m1：");
scanf("%d%d", &b1, &m1);
printf("请输入b2和m2：");
scanf("%d%d", &b2, &m2);
// 计算M1和M2
M1 = m1 * m2;
M2 = m2 * m1;
// 计算y1和y2
for (int i = 1; i < m1; i++)
{
if ((M1 / m1) * i % m1 == 1)
{
y1 = (M1 / m1) * i;
break;
}
}
for (int i = 1; i < m2; i++)
{
if ((M2 / m2) * i % m2 == 1)
{
y2 = (M2 / m2) * i;
break;
}
}
// 计算x
x = (b1 * M2 * y2 + b2 * M1 * y1) % (M1 * M2);
printf("同余式组的解为：x=%d\n", x);
return 0;
}

用C语言编程实现计算同余式组x≡b1(mod m1),x≡b2(mod m2)的解

### 回答1：

#include <stdio.h>

int main() {
    int b1, b2, m1, m2, x;
    printf("请输入b1, m1, b2, m2：\n");
    scanf("%d%d%d%d", &b1, &m1, &b2, &m2);
    for (int i = 0; i < m1 * m2; i++) {
        if (i % m1 == b1 && i % m2 == b2) {
            x = i;
            break;
        }
    }
    printf("x ≡ %d (mod %d)\n", x, m1 * m2);
    return 0;
}

这个程序中，我们通过枚举x的值，找到满足同余式组的解。具体来说，我们从0开始枚举x的值，每次判断x是否同时满足两个同余式，如果满足则将其作为解并退出循环。

需要注意的是，当m1和m2不互质时，同余式组可能无解或有多个解。此时需要使用扩展欧几里得算法来求解。

### 回答2：
要用C语言编程实现计算同余式组x≡b1(mod m1),x≡b2(mod m2)的解，可以使用中国剩余定理（Chinese Remainder Theorem，CRT）来实现。

1. 首先，定义一个函数findCRT，该函数接受四个参数：b1、m1、b2、m2，表示两个同余式的余数和模数。
2. 在findCRT函数中，先判断m1和m2是否互质（即最大公约数是1）。若不互质，则无解；若互质，则继续执行下一步。
3. 计算m1和m2的乘积，记为M = m1 * m2。
4. 分别计算M除以m1和m2的商，记为q1 = M / m1和q2 = M / m2。
5. 计算q1关于m1的模反元素x1（即满足x1 * q1 ≡ 1 (mod m1)），可以使用扩展欧几里德算法来求解。
6. 同样地，计算q2关于m2的模反元素x2。
7. 根据中国剩余定理，x ≡ (b1 * q1 * x1 + b2 * q2 * x2) (mod M)即为同余式组的解。
8. 返回计算得到的解x。

以下是一个示例代码：

#include <stdio.h>

int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int findModInverse(int a, int m) {
    int m0 = m, t, q;
    int x0 = 0, x1 = 1;

    if (m == 1)
        return 0;

    while (a > 1) {
        q = a / m;
        t = m;

        m = a % m;
        a = t;

        t = x0;

        x0 = x1 - q * x0;
        x1 = t;
    }

    if (x1 < 0)
        x1 += m0;

    return x1;
}

int findCRT(int b1, int m1, int b2, int m2) {
    int M = m1 * m2;
    int q1 = M / m1;
    int q2 = M / m2;
    int x1 = findModInverse(q1, m1);
    int x2 = findModInverse(q2, m2);

    int x = (b1 * q1 * x1 + b2 * q2 * x2) % M;

    return x;
}

int main() {
    int b1, m1, b2, m2;
    printf("输入b1、m1、b2、m2的值:");
    scanf("%d %d %d %d", &b1, &m1, &b2, &m2);

    int x = findCRT(b1, m1, b2, m2);
    printf("同余式组的解为: x ≡ %d (mod %d)\n", x, m1 * m2);

    return 0;
}

以上代码中的函数gcd用于求最大公约数，函数findModInverse用于求模反元素x。在main函数中，通过用户输入获取同余式组的参数，然后调用findCRT函数计算解，并打印结果。

### 回答3：
要用C语言编程实现计算同余式组x≡b1(mod m1),x≡b2(mod m2)的解，可以使用中国剩余定理（Chinese Remainder Theorem）。以下是C语言的实现代码：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int extendedEuclidean(int a, int b, int *x, int *y)
{
    if (a == 0)
    {
        *x = 0;
        *y = 1;
        return b;
    }

    int x1, y1;
    int gcd = extendedEuclidean(b % a, a, &x1, &y1);

    *x = y1 - (b/a) * x1;
    *y = x1;
    
    return gcd;
}

int chineseRemainder(int b1, int m1, int b2, int m2)
{
    int x, y;
    int gcd = extendedEuclidean(m1, m2, &x, &y);

    int lcm = (m1 * m2) / gcd;
    int result = (b1 * m2 * y + b2 * m1 * x) % lcm;

    return result;
}

int main()
{
    int b1, m1, b2, m2;
    printf("请输入同余式组的参数：\n");
    printf("x≡b1(mod m1)\n");
    printf("x≡b2(mod m2)\n");
    scanf("%d%d%d%d", &b1, &m1, &b2, &m2);

    int result = chineseRemainder(b1, m1, b2, m2);

    printf("同余式组的解为：x ≡ %d (mod %d)\n", result, m1 * m2);

    return 0;
}

这个程序会要求用户输入同余式组的参数b1，m1，b2，m2。然后，通过调用`chineseRemainder`函数来计算出同余式组的解，并将结果输出到屏幕上。

值得注意的是，这里的代码使用了扩展欧几里得算法来计算乘法逆元，并且假设输入的m1和m2互质。如果输入的m1和m2不互质，这个代码需要进行适当的修改。