AcWing 204. 表达整数的奇怪方式（线性同余方程组）打卡

雨点打透心脏的1/2处 2021-11-14 12:26 263阅读 0赞

给定2n个整数a1,a2,…,ana1,a2,…,an和m1,m2,…,mnm1,m2,…,mn,求一个最小的整数x，满足∀i∈\[1,n\],x≡mi(mod ai)∀i∈\[1,n\],x≡mi(mod ai)。

#### 输入格式 ####

第1行包含整数n。

第2..n行：每i+1行包含两个整数aiai和mimi,数之间用空格隔开。

#### 输出格式 ####

输出整数x，如果x不存在，则输出-1。

#### 数据范围 ####

1≤ai≤231−11≤ai≤231−1,  
0≤mi<ai0≤mi<ai

#### 输入样例： ####

2
    8 7
    11 9

#### 输出样例：`31` ####

题意：求出同时满足所有式子要求的最小整数x,如果不存在输出-1
    思路：首先没说m互相互质，所以这不是中国剩余定理，这是线性同余方程组问题
    
    这里摘抄一位大佬的

中国剩余定理，又名孙子定理o(\*≧▽≦)ツ

能求解什么问题呢？

问题：

一堆物品

3个3个分剩2个

5个5个分剩3个

7个7个分剩2个

问这个物品有多少个

解这题，我们需要构造一个答案

我们需要构造这个答案

5\*7\*inv(5\*7,  3) % 3  =  1

3\*7\*inv(3\*7,  5) % 5  =  1

3\*5\*inv(3\*5,  7) % 7  =  1

这3个式子对不对

显然这里就要用到线性同余方程用扩欧来求解

然后两边同乘你需要的数

2 \* 5\*7\*inv(5\*7,  3) % 3  =  2

3 \* 3\*7\*inv(3\*7,  5) % 5  =  3

2 \* 3\*5\*inv(3\*5,  7) % 7  =  2

令

a = 2 \* 5\*7\*inv(5\*7,  3)

b = 3 \* 3\*7\*inv(3\*7,  5)

c = 2 \* 3\*5\*inv(3\*5,  7)

那么

a % 3 = 2

b % 5 = 3

c % 7 = 2

其实答案就是a+b+c

因为

a%5 = a%7 = 0 因为a是5的倍数，也是7的倍数

b%3 = b%7 = 0 因为b是3的倍数，也是7的倍数

c%3 = c%5 = 0 因为c是3的倍数，也是5的倍数

所以

(a + b + c) % 3 = (a % 3) + (b % 3) + (c % 3) = 2 + 0 + 0 = 2

(a + b + c) % 5 = (a % 5) + (b % 5) + (c % 5) = 0 + 3 + 0 = 3

(a + b + c) % 7 = (a % 7) + (b % 7) + (c % 7) = 0 + 0 + 2 = 2

你看你看，答案是不是a+b+c(｡･ω･)ﾉﾞ，完全满足题意

但是答案，不只一个，有无穷个，每105个就是一个答案（105 = 3 \* 5 \* 7）

根据计算，答案等于233,233%105 = 23

如果题目问你最小的那个答案，那就是23了

结论：因为我要同时满足多个式子的要求，那么我们来一个一个来满足，当前的余数我就用其他数来拼凑

因为是其他数的乘积，那么其他数mod的话都会等于0，然后只有当前数会有余数，这样就能得出一个其他所有数mod等于0，满足当前数余数要求的数了

然后我们用这个方法给每个数都求一个这样的数，然后求和，那么就能满足所有数的要求了，当然这只限于两两互质情况

**不互质的中国剩余定理  -  线性同余方程组**

首先为什么要互质呢

因为如果化简成最简质因子的话，如果有相同质因子，那么有可能会mod成0，那么我们也不能借用来获取自己想要的数了

如

x = 2 mod 4

x = 3 mod 6

x = 4 mod 8

6\*8%4 = 0 ,所以就不行了

这里我们要用线性同余方程组，来两两合并，最后化简成一个来得出答案

![1386557-20190626084524833-224536752.png][]

然后我们就可以得出推导式

#include<cstdio>
    #include<string>
    #include<cstring>
    #include<cmath>
    #include<iostream>
    #include<algorithm>
    #include<map>
    #include<vector>
    #define LL long long
    using namespace std;
    LL m[1000],r[1000];
    void ex_gcd(LL a,LL b,LL &d,LL &x,LL &y)
    {
        if(b==0){ x=1;y=0;d=a;return ;}
        ex_gcd(b,a%b,d,y,x);  y-=x*(a/b);
    }
    LL gcd(LL a,LL b)
    {
        return b==0?a:gcd(b,a%b);
    }
    LL ex_CRT(int n)
    {
        LL a,b,c,c1,c2,x,y,d,N;
        a=m[1];  c1=r[1];
        for(int i=2;i<=n;i++){
            b=m[i];c2=r[i]; c=c2-c1;
            ex_gcd(a,b,d,x,y);
            if(c%d)  return -1;
            LL b1=b/d;//转移式
            x=((c/d*x)%b1+b1)%b1;//
            c1=a*x+c1; a=a*b1;//
        }
        /*if(c1==0){
            c1=1; for(int i=1;i<=n;i++) c1=c1*m[i]/gcd(c1,m[i]);  //如果题目要求要正整数，那么加上一个所有数的最小公倍数
        }*/
        return c1;
    }
    int main()
    {
        int T,n,Case=0;
        scanf("%d",&n);
        
        for(int i=1;i<=n;i++)  scanf("%lld%lld",&m[i],&r[i]);
       // LL c1=1; for(int i=1;i<=n;i++) c1=c1*m[i]/gcd(c1,m[i]);
        printf("%lld\n",ex_CRT(n));
        return 0;
    }

转载于:https://www.cnblogs.com/Lis-/p/11087856.html

[1386557-20190626084524833-224536752.png]: /images/20211114/aa6c429838174061aef17492295f6c06.png