中国剩余定理的应用:表达整数的奇怪方式

什么是中国剩余定理呢?

中国剩余定理的应用:表达整数的奇怪方式

 当m1,m2,....mn的值两两互质的时候,求x的值。

假设 M = m1 * m2 * ... * mn

在设 Hi = M / mi (也就是除了mi之外,其他的m值的乘积)

由于m1,m2...mn两两互质, 所以Hi与mi是互质的。

那么Hi ^ (-1)  也就是 Hi 关于 mod mi 的逆元是存在的。

(使用扩展欧几里得算法进行求解这个逆元,因为当下只有Hi,与mi互质这一个条件

也就是  Hi * (Hi ^ -1)  + y * mi = 1  使用扩展欧几里得算法将x求出,也就是Hi ^ -1)

则: x = a1 * H1 * ( H1 ^ -1) + a2 * H2 * (H2 ^ -1) + ... + ak * Hk * (Hk ^ -1).  (这个就是中国剩余定理的一个通用公式,但是应用的前提条件是,m1,m2,m3...两两互质。)

 

以第一个方程 mod m1为例:

H1 * H ^( -1) mod m1 == 1 , 而其他的H2,H3....中都包含了m1,所以mod m1为0.

所以 x = a1 * a mod m1 . 成立。

那么问题来了:

如果m1,m2,m3...不两两互质呢。那就要用到中国剩余定理的思想,将两两方程不断合并,最后就变为了一个方程了。

中国剩余定理的应用:表达整数的奇怪方式

还是这些方程,但是现在没有m1,m2...两两互质。该怎么办呢?

先取出前面两个方程出来。并换一种表现形式

x == k1 * m1 + a1 

x == k2 * m2 + a2

那么也就是说明了

k1 * m1 + a1 == k2 * m2 + a2

--->k1 * m1 - k2 * m2 == a2 - a1

这就可以用扩展欧几里得的方式求解出一组k1,k2出来。

但是要存在有解 则 (a2 - a1) 能够整除 gcd(m1,m2);

 所以真正的k1就是 k1 =k1 *  (a2 - a1) / gcd(m1,m2);

而k1的通解是, k1 + k * (m2 / gcd(m1,m2));

则将k1的通解带入到方程中,就可以得到一个新的关于x的方程

x == ( k1 + k * (m2 / gcd(m1,m2))  ) * m1 + a1;

x == k1 * m1 + a1  + k * m1 * m2 / gcd(m1,m2);

x == k1 * m1 + a1 + k * lcm【m1,m2】 (lcm【m1,m2】为m1,m2的最小公倍数)

而k1 * m1 + a1 就是 新的 a1(而这个k1 * m1 + a1不就是我们每次以第一个公式作为合并基准的公式嘛) ,  而 lcm【m1,m2】就是新的m1 

而这个x 就是前两个方程合并 后 得到的一个新的方程。

同样,新的方程 和 第三个方程合并又可以将两个方程变为一个方程,以此类推,直到最后只剩下一个方程。

这个m1,m2,a1,k1已经在合并过程中不断发生了变化。

x == k1 * m1 + a1 + k * lcm【m1,m2】

得到的最后一个这个公式的m1和a1

实际上就是 x mod m1 == a1的含义了。

而我们要求出这个最后一个公式的其中一个满足条件的x.

所以取 x = ( a1 % m1 + m1) % m1即可。 

题目链接:https://www.acwing.com/problem/content/206/

题目:

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

输入格式

第 1 行包含整数 n。

第 2…n+1 行:每 i+1 行包含两个整数 ai和 mi,数之间用空格隔开。

输出格式

输出最小非负整数 x,如果 x不存在,则输出 −1。
如果存在 x,则数据保证 x 一定在 64 位整数范围内。

数据范围

1≤ai≤2e31 - 1,
0≤mi<ai
1≤n≤25

输入样例:

2
8 7
11 9

输出样例:

31

分析:

按照上面m1,m2,m3...不一定互质的分析来就可以了。

但是要注意,此题是中国剩余定理的应用:表达整数的奇怪方式 

不要和上面的m和a混淆了。 

最后此题会变为:

x == k1 * a1 + m1 + k * lcm[a1,a2]

新的m1 为 k1 * a1 + m1

新的a1为 lcm[a1.a2];

代码实现:

# include <iostream>
using namespace std;

int n;

long long exgcd(long long a ,long long b , long long & x , long long & y)
{
    if(!b)
    {
        x = 1 , y = 0;
        return a;
    }
    else
    {
        int t = exgcd(b,a % b , y , x);
        y -= a / b * x;
        return t;
    }
}

int main()
{
    scanf("%d",&n);
    bool flag = true;
    long long a1,m1,a2,m2;
    
    scanf("%lld %lld",&a1,&m1); // 先存入第一个方程,我们的合并是通过两个两个不断和并为1个最后化为一个方程
    for(int i = 2 ; i <= n ; i++)
    {
        scanf("%lld %lld",&a2,&m2);
        long long k1,k2;
        long long t = exgcd(a1,a2,k1,k2);
        if((m2 - m1) % t)  // 无解
        {
            flag = false;
            break;
        }
        else
        {
            k1 = (m2 - m1) / t * k1; //真正的k1,k2
            k2 = (m2 - m1) / t * k2; // 而k2实际上用不到
            
            k1 = ( k1 % (a2 / t) + a2 / t ) % (a2 / t); // 最小的正整数k1, 为了防止其爆long long,k1尽量取小
            
            
            m1 = k1 * a1 + m1;
            a1 =  a1 / t * a2; // 新的a1为 a1,a2的最小公倍数
        }
    }
    if(flag)
    {
        printf("%lld\n",(m1 % a1 + a1) % a1);
    }
    else
    {
        printf("-1\n");
    }
    return 0;
}
上一篇:redis操作7 对存储HyperLogLog的操作(计算不重复数个数)


下一篇:Redis-01-基础