扩展中国剩余定理详解

前言

阅读本文前,推荐先学一下中国剩余定理。其实不学也无所谓,毕竟两者没啥关系

扩展CRT

我们知道,中国剩余定理是用来解同余方程组

\begin{cases}x\equiv c_{1}\left( mod\ m_{1}\right) \\ x\equiv c_{2}\left( mod\ m_{2}\right) \\ \ldots \\ x\equiv c_r\left( mod\ m_r\right) \end{cases}

但是有一个非常令人不爽的事情就是它要求m_1,m_2\ldots,m_r两两互素

如果某个毒瘤出题人偏要求它们部互素呢?

其实也有解决的办法

就是把出题人吊起来干一顿用扩展中国剩余定理

扩展中国剩余定理跟中国剩余定理没半毛钱关系,一个是用扩展欧几里得,一个是用构造

首先我们还是从简单入手,考虑一下如果同余方程组只有两个式子的情况

x\equiv c_{1}\left( mod\ m_{1}\right) \\ x\equiv c_{2}\left( mod\ m_{2}\right)

将两个式子变形

x=c_{1}+m_{1}k_{1}\\ x=c_{2}+m_{2}k_{2}

联立

c_{1}+m_{1}k_{1}=c_{2}+m_{2}k_{2}

移项

m_{1}k_{1}=c_{2}-c_{1}+m_{2}k_{2}

我们用$(a,b)$表示$a,b$的最大公约数

在这里需要注意,这个方程有解的条件是

\left( m_{1},m_{2}\right) |\left( c_{2}-c_{1}\right),因为后面会用到\dfrac {\left( c_{2}-c_{1}\right) }{\left( m_{2},m_{1}\right) }这一项,如果不整除的话肯定会出现小数。

对于上面的方程,两边同除$(m_1,m_2)$

\dfrac {m_{1}k_{1}}{\left( m_{1},m_{2}\right) }=\dfrac {c_{2}-c_{1}}{\left( m_{1},m_{2}\right) }+\dfrac {m_{2}k_{2}}{\left( m_{1},m_{2}\right) }

\dfrac {m_{1}}{\left( m_{1},m_{2}\right) }k_{1}=\dfrac {c_{2}-c_{1}}{\left( m_{1},m_{2}\right) }+\dfrac {m_{2}}{\left( m_{1},m_{2}\right) }k_{2}

转换一下

\dfrac {m_{1}}{\left( m_{1},m_{2}\right) }k_{1} \equiv \dfrac {c_{2}-c_{1}}{\left( m_{1},m_{2}\right) } (mod\ \dfrac {m_{2}}{\left( m_{1},m_{2}\right) })

此时我们已经成功把$k_2$消去了。

同余式两边同除\dfrac {m_{1}}{\left( m_{1},m_{2}\right) }

k_1\equiv inv({m_1\over(m_1,m_2)},{m_2\over (m_1,m_2)})*{(c_2-c_1)\over (m_1,m_2)}\pmod {{m_2\over(m_1,m_2)}}

inv(a,b)表示a在模b意义下的逆元

k_1=inv({m_1\over(m_1,m_2)},{m_2\over (m_1,m_2)})*{(c_2-c_1)\over (m_1,m_2)}+{{m_2\over (m_1,m_2)}}*y

接下来怎么办呢?这个式子已经化到最简了。。

不要忘了,我们刚开始还有两个式子。我们把k_1待回去!

x=inv({m_1\over(m_1,m_2)},{m_2\over (m_1,m_2)})*{(c_2-c_1)\over (m_1,m_2)}*m_1+y{{m_1m_2\over (m_1,m_2)}}+c_1

x\equiv inv({m_1\over(m_1,m_2)},{m_2\over (m_1,m_2)})*{(c_2-c_1)\over (m_1,m_2)}*m_1+c_1\pmod {{m_1m_2\over (m_1,m_2)}}

此时,整个式子中的元素我们都已经知道了

具体一点,这个式子可以看做是x\equiv c\pmod m

其中c=(inv({m_1\over (m_1,m_2)},{m_2\over (m_1,m_2)})*{(c_2-c_1)\over (m_1,m_2)})\%{m_2\over (m_1,m_2)}*m_1+c_1

m={m_1m_2\over (m_1,m_2)}

推广一下

我们每次把两个同余式合并,求解之后得到一个新的同余式。再把新的同余式和其他的联立,最终就可以求出满足条件的解

代码

题目链接

#include<iostream>
#include<cstdio>
#define LL long long 
using namespace std;
const LL MAXN=1e6+10;
LL K,C[MAXN],M[MAXN],x,y;
LL gcd(LL a,LL b)
{
    return b==0?a:gcd(b,a%b);
}
LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(b==0){x=1,y=0;return a;}
    LL r=exgcd(b,a%b,x,y),tmp;
    tmp=x;x=y;y=tmp-(a/b)*y;
    return r;
}
LL inv(LL a,LL b)
{
    LL r=exgcd(a,b,x,y);
    while(x<0) x+=b;
    return x;
}
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else
    #endif
    while(~scanf("%lld",&K))
    {
        for(LL i=1;i<=K;i++) scanf("%lld%lld",&M[i],&C[i]);
        bool flag=1;
        for(LL i=2;i<=K;i++)
        {
            LL M1=M[i-1],M2=M[i],C2=C[i],C1=C[i-1],T=gcd(M1,M2);
            if((C2-C1)%T!=0) {flag=0;break;}
            M[i]=(M1*M2)/T;
            C[i]= ( inv( M1/T , M2/T ) * (C2-C1)/T ) % (M2/T) * M1 + C1;
            C[i]=(C[i]%M[i]+M[i])%M[i];
        }
        printf("%lld\n",flag?C[K]:-1);
    }
    return 0;
}

再放道裸题

http://acm.hdu.edu.cn/showproblem.php?pid=1573

题解

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大数据挖掘DT机器学习

用R语言做数据清理(详细教程)

数据的清理 如同列夫托尔斯泰所说的那样:“幸福的家庭都是相似的,不幸的家庭各有各的不幸”,糟糕的恶心的数据各有各的糟糕之处,好的数据集都是相似的。一份好的,干净...

85150
来自专栏Small Code

Python-NumPy基础

前言 这两天读完《利用Python进行数据分析》 这本书的第4章:NumPy 基础:数组和矢量计算 后,在进行下一步阅读高级应用前,先整理本章内容,做个笔记备查...

348100
来自专栏量子位

谷歌云TPU上可以用Julia啦!0.23秒跑100张图片,Jeff Dean点赞推荐

不久前,Julia Computing官方放出了一篇论文,展示将Julia代码和机器学习模型编译到谷歌云TPU的方法,可以实现在0.23秒内完成100张图片VG...

13130
来自专栏数据结构与算法

2727:仙岛求药

2727:仙岛求药 查看 提交 统计 提问 总时间限制:1000ms内存限制:65536kB描述少年李逍遥的婶婶病了,王小虎介绍他去一趟仙灵岛,向仙女姐姐要仙丹...

31580
来自专栏潇涧技术专栏

Python Algorithms - C7 Greedy

Python算法设计篇(7) Chapter 7: Greed is good? Prove it!

12920
来自专栏数据魔术师

干货 | 遗传算法(Genetic Algorithm) Java 详细代码及注释

2.5K70
来自专栏大数据挖掘DT机器学习

python数据分析师面试题选

python数据分析部分 1. 如何利用SciKit包训练一个简单的线性回归模型 利用linear_model.LinearRegression()函数 #...

70860
来自专栏冰霜之地

Google S2 中的 CellID 是如何生成的 ?

笔者在《高效的多维空间点索引算法 — Geohash 和 Google S2》文章中详细的分析了 Google S2 的算法实现思想。文章发出来以后,一部分读者...

41220
来自专栏云时之间

NLP系列学习:常用的语言平滑模型

语言模型常见的平滑算法就那几种,一般的教程都不提分几种的模式、分类。 不过在MIT的NLP课程ppt中总结说有三种模式:Discounting, Interp...

32260
来自专栏生信技能树

二代测序数据拼接之原理篇

前前后后接触了一些基因组和转录组拼接的工作,而且后期还会持续进行。期间遇到了各种各样莫名其妙的坑,也尝试了一些不同的方法和软件,简单做一个阶段性小结,本篇是原理...

1.7K50

扫码关注云+社区

领取腾讯云代金券