# 扩展中国剩余定理详解

## 扩展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}

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}

\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) }这一项，如果不整除的话肯定会出现小数。

\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_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

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)}}

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 条评论

• ### POJ 2891 Strange Way to Express Integers

Description Elina is reading a book written by Rujia Liu, which introduces a ...

• ### 11.6NOIP模拟赛解题报告

很显然的一个贪心是从左往右扫，如果遇到一个不合法的点$$i$$，那么升级$$i + R$$处的炮台。。

• ### 洛谷P3383 【模板】线性筛素数(Miller_Rabin)

题目描述 如题，给定一个范围N，你需要处理M个某数字是否为质数的询问（每个数字均在范围1-N内） 输入输出格式 输入格式： 第一行包含两个正整数N、M，分别表示...

• ### POJ 2891 Strange Way to Express Integers

Description Elina is reading a book written by Rujia Liu, which introduces a ...

• ### POJ 2773 Happy 2006（容斥原理+二分）

Happy 2006 Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 1...

• ### 打表法——暴力破解方法之一

特别声明：除特别标注，本站文章均为原创，本站文章原则上禁止转载，如确实要转载，请电联：wangyeuuu@qq.com，尊重他人劳动成果，谢过~

• ### 11.6NOIP模拟赛解题报告

很显然的一个贪心是从左往右扫，如果遇到一个不合法的点$$i$$，那么升级$$i + R$$处的炮台。。

• ### 洛谷P3383 【模板】线性筛素数(Miller_Rabin)

题目描述 如题，给定一个范围N，你需要处理M个某数字是否为质数的询问（每个数字均在范围1-N内） 输入输出格式 输入格式： 第一行包含两个正整数N、M，分别表示...

• ### 『数学』--数论--组合数+卢卡斯定理+扩展卢卡斯定理

卢卡斯定理： 求 C ...