problem
求这个关于 \(x\) 的方程组的最小正整数解：
\[\begin{cases}
x\equiv b_1 \pmod{a_1}\\
x\equiv b_2 \pmod{a_2}\\
x\equiv b_3 \pmod{a_3}\\
\cdots\\
x\equiv b_n \pmod{a_n}\\
\end{cases}\]
中国剩余定理 CRT
适用范围：\(a_1,a_2,\cdots,a_n\) 两两互质。
做法：令 \(M=\prod a_i,m_i=M/a_i\)，然后 \(t_i\) 是 \(m_i\) 在模 \(a_i\) 意义下的逆元。
答案是 \(x=\sum b_im_it_i\)。对 \(M\) 取模。
证明：当 \(x\bmod a_i\) 是，对于不是 \(i\) 的项会因为 \(a_i|m_j\) 变为 \(0\)，对于 \(i\) 会因为逆元变为 \(1\)。
点击查看代码
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
LL mod(LL x,LL m){return(x%m+m)%m;}
LL exgcd(LL a,LL b,LL c,LL& x,LL& y){
if(!b) return x=c/a,y=0,a;
LL res=exgcd(b,a%b,c,y,x);
return y-=a/b*x,res;
}
LL solve(LL a,LL b,LL c){
LL x,y,d=exgcd(a,b,c,x,y);
return c%d==0?mod(x,b/d):-1;
}
int n,a[20],b[20];
LL M=1,ans;
int main(){
// #ifdef LOCAL
// freopen("input.in","r",stdin);
// #endif
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]),M*=a[i];
for(int i=1;i<=n;i++){
LL mi=M/a[i];
ans+=1ll*b[i]*mi*solve(mi,a[i],1);
}
printf("%lld\n",ans%M?ans%M:M);
return 0;
}
扩展中国剩余定理 EXCRT
和 CRT 一点关系没有。
考虑暴力。现在考虑的方程组的 \(a_i\) 的 \(lcm\) 为 \(L\)，当前一个合法答案为 \(x\)。
加入一个新的方程组，我们不断地使得 \(x\to x+L\)，等到 \(x\equiv b_i\pmod{a_i}\) 时停止。
考虑优化，设要加 \(b\) 次，解一个方程：\(x+bL\equiv b_i\pmod{a_i}\to \boxed{a_i}c+\boxed{L}b=\boxed{b_i-x}\)。
等式两边有一些系数可以对 \(a_i\) 取模。然后用 exgcd 求出它的最小非负整数解。【模板】exgcd
点击查看代码
模板题很有可能爆 long long。我不想改了。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
LL mod(LL x,LL m){return(x%m+m)%m;}
LL exgcd(LL a,LL b,LL c,LL& x,LL& y){
if(!b) return x=c/a,y=0,a;
LL res=exgcd(b,a%b,c,y,x);
y-=a/b*x;
return res;
}
LL solve(LL a,LL b,LL c,LL x=0,LL y=0){
return c%exgcd(a,b,c,x,y)==0?mod(x,b):-1;
}
LL lcm(LL a,LL b){
LL x,y;
return a/exgcd(a,b,1,x,y)*b;
}
LL n,ans,tot=1;
bool update(LL a,LL b){
// while(ans%a!=b) ans+=tot;
// ans+kt=b(mod a)=>tk+ay=b-ans
LL z=solve(mod(tot,a),a,mod(b-ans,a));
if(z==-1) return 0;
ans+=z*tot,tot=lcm(tot,a),ans=mod(ans,tot);
return 1;
}
int mian(){
bool flag=0;
for(int i=1;i<=n;i++){LL a,b;
scanf("%lld%lld",&a,&b);
if(!update(a,b)) flag=1;
}
long long x=ans;
printf("%lld\n",x);
return 0;
}
void reset(){
ans=0,tot=1;
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
while(~scanf("%d",&n)) reset(),mian();
return 0;
}