这是一道中国剩余定理（又名孙子定理、CRT）的模板题。
它最早来自于「孙子算经」，形式化的说，它是一种用于求解如下的线性同余方程组的解的算法。
$$ \left\{ \begin{matrix}x\equiv a_{1} \pmod{p_1} \\x\equiv a_{2}\pmod{p_2}\\\cdots\\x\equiv a_{n}\pmod{p_i}\end{matrix} \right.$$
我们令：
$$\begin{equation}\begin{split}P&=&\prod_{i=1}^{n}p_{i}\\t_{i},st: \frac{P}{p_{i}}t_{i}&\equiv &1\pmod{p_i}\\\exists x,st: x&\equiv &\sum_{i=1}^n \frac{P}{p_{i}}a_{i}t_{i}\\x&\in&\{x_0+kP,k\in Z\pmod{P}\}\end{split}\end{equation}$$
然而这是怎么证明的呢？我们有如下推导：
$$\begin{equation}\begin{split}\forall i,\forall j,st:i\neq j, a_{i}t_{i}\frac{P}{p_{i}}&\equiv&0&\pmod{p_i}\\a_{i}t_{i}\frac{P}{p_i}&\equiv&a_{i} &\pmod{p_i}\\\forall j,\sum_{i=1}^{n}a_{i}t_{i}\frac{P}{p_{i}}&\equiv&a_{j}t_{j}\frac{P}{p_{j}} \equiv a_{j}&\pmod{p_{j}}\\\exists x_0&\equiv& \sum_{i=1}^{n}a_{i}t_{i}\frac{P}{p_{i}}&\pmod{p_{j}}\\\end{split}\end{equation}$$
故而我们就可以求得上述方程的最小正整数解。
另外，看到这题的数据范围就可以猜到又是龟速乘登场的时刻了。
这一题还有个坑点就是读入的数可能是负数…
#include<iostream>
#include<cstdio>
long long MOD=1;
inline long long mlt(long long A,long long X){
long long BS=A,RT=0;
while(X){
if(X&1){
RT+=BS;
RT%=MOD;
}
BS+=BS;
BS%=MOD;
X>>=1;
}
return RT;
}
inline long long exgcd(long long A,long long B,long long &X,long long &Y,long long D=0){
return B?(D=exgcd(B,A%B,Y,X),Y-=A/B*X,D):(X=1,Y=0,A);
}
inline long long pw(long long A,long long X){
long long BS=A,RT=1;
while(X){
if(X&1){
RT=mlt(RT,BS)%MOD;
}
BS=mlt(BS,BS)%MOD;
X>>=1;
}
return RT;
}
long long n,a[100005],b[100005];
void init(){
scanf("%lld",&n);
for(int i=1;i<=n;++i){
scanf("%lld",&a[i]);
}
for(int i=1;i<=n;++i){
scanf("%lld",&b[i]);
a[i]=(a[i]%b[i]+b[i])%b[i];//注意负数！！
MOD*=b[i];
}
long long X,Y,T,ans=0;
for(int i=1;i<=n;++i){
T=MOD/b[i];
exgcd(T,b[i],X,Y);
X=(X%b[i]+b[i])%b[i];;
ans=(ans+mlt(mlt(T,X),a[i]))%MOD;
}
printf("%lld\n",(ans+MOD)%MOD);
}
int main(){
init();
return 0;
}
