@Junlier
2018-10-03T19:45:56.000000Z
字数 2373
阅读 3396
数学方法——数论
阅读体验:https://zybuluo.com/Junlier/note/1300035
前置知识点:
这两个东西都是用来解同余方程组的
形如
心理准备:这里我觉得自己讲得不是很清晰,有点说不清的感觉
在上述方程中,存在一种特殊情况,即全部互质
有什么用呢,用处就是可以用中国剩余定理(孙子定理)
首先,古人告诉我们:
解上面那个方程相当于对于每一个:
把变成,其他的变成的解
然后答案就是
也就是解每一个形如下面的方程组的解在乘上:
别问我为什么,我不知道
那么考虑怎么求呢?
记为
显然解必须是的倍数
那么方程变为
lst CRT()
{
lst tot=1,Ans=0;
for(int i=1;i<=n;++i)tot*=W[i];
for(int i=1;i<=n;++i)
{
lst now=tot/W[i],x,y;
Exgcd(now,W[i],x,y);//不需要我讲吧!
x=(x%W[i]+W[i])%W[i];//这个取膜貌似很关键诶
Ans=(Ans+Mult(Mult(x,now,tot),B[i],tot)+tot)%tot;//Mult是快速乘
}return Ans>=0?Ans:Ans+tot;
}
再把方程组放一遍:
#include<bits/stdc++.h>
#define lst long long
#define ldb double
#define N 100050
using namespace std;
const int Inf=1e9;
lst read()
{
lst s=0,m=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')m=1;ch=getchar();}
while( isdigit(ch))s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return m?-s:s;
}
lst n,Ans,x,y,M;
lst A[N],B[N];
lst qmul(lst x,lst y,lst p)
{
lst ret=0;
while(y)
{
if(y&1)ret=(ret+x)%p;
x=(x+x)%p;y>>=1;
}return ret;
}
lst Exgcd(lst a,lst b,lst &x,lst &y)
{
if(!b){x=1,y=0;return a;}
lst ss=Exgcd(b,a%b,x,y),t;
t=x,x=y,y=t-(a/b)*y; return ss;
}
int main()
{
n=read();
for(int i=1;i<=n;++i)
B[i]=read(),A[i]=read();
Ans=A[1],M=B[1];
//根据上面的详解一步对应一行
for(int i=2;i<=n;++i)
{
lst Get=((A[i]-Ans)%B[i]+B[i])%B[i];
lst GCD=Exgcd(M,B[i],x,y);
x=qmul(x,Get/GCD,B[i]);//qmul是龟速乘
Ans+=M*x;
M*=B[i]/GCD;//这里是更新辅助下一次计算
Ans=(Ans+M)%M;
}printf("%lld\n",Ans);
return 0;
}