https://www.luogu.org/problemnew/show/P3868
现有两组数字，每组k个，第一组中的数字分别为：a1，a2，...，ak表示，第二组中的数字分别用b1，b2，...，bk表示。其中第二组中的数字是两两互素的。求最小的非负整数n，满足对于任意的i，n - ai能被bi整除。
所有数据中，第一组数字的绝对值不超过$10^9$（可能为负数），第二组数字均为不超过6000的正整数，且第二组里所有数的乘积不超过$10^{18}$
孙子定理的练手题……
套公式，解是
\[x\equiv \sum_{i=i}^n M_iM‘_ia_i\pmod{\prod_{i=1}^nb_i}\]
其中
\[M_i=\frac{\prod_{j=1}^nb_j}{b_i},M‘_iM_i\equiv1\pmod{b_i}\]
那么直接求和就好了，还需要注意爆long long（通过qmul解决），用qmul需要注意乘号右边不能小于0，否则是未定义行为……（G++直接死循环）
求逆的时候需要注意不能直接用费马小定理，因为b不一定是素数，$\varphi(b)\ne{b-1}$！
所以只能用EXGCD，但是还是要注意得出来的结果并不保证大于0，所以放右边要注意换为大于0的数字（就算放左边a又要小于0，需要处理a了……）
AC代码
#include<cstdio>
#include<cstdlib>
#include<cctype>
#include<cstring>
#include<algorithm>
#include<set>
#define REP(r,x,y) for(register int r=(x); r<(y); r++)
#define REPE(r,x,y) for(register int r=(x); r<=(y); r++)
#define PERE(r,x,y) for(register int r=(x); r>=(y); r--)
#ifdef sahdsg
#define DBG(...) printf(__VA_ARGS__),fflush(stdout)
#else
#define DBG(...) (void)0
#endif
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
char ch; int si;
#define gc() getchar()
template<class T>
inline void read(T &x) {
x=0; si=1; for(ch=gc();!isdigit(ch) && ch!=‘-‘;ch=gc());
if(ch==‘-‘){si=-1,ch=gc();} for(;isdigit(ch);ch=gc())x=x*10+ch-‘0‘;
x*=si;
}
template<class T, class...A> inline void read(T &x, A&...a){read(x); read(a...);}
inline LL qmul(LL a, LL b, LL p) {
LL ans=0;
for(;b;b>>=1) {
if(b&1) ans=(ans+a)%p;
a=(a*2)%p;
}
return ans;
}
inline void exgcd(LL a, LL b, LL &x, LL &y) {
if(b==0) {x=1, y=0; return;}
exgcd(b,a%b,y,x);
y-=a/b*x;
//return d;
}
#define MAXN 17
LL a[MAXN],b[MAXN],M[MAXN],M_[MAXN];
LL B=1;
int main() {
#ifdef sahdsg
freopen("in.txt","r",stdin);
#endif
int k; read(k);
REP(i,0,k) {read(a[i]);}
REP(i,0,k) {read(b[i]); B*=b[i];}
LL ans=0;
REP(i,0,k) {
//B/b[i] === 1 mod b[i]
//B/b[i]x+b[i]*y=1
LL x,t;
exgcd(B/b[i],b[i],x,t);
x%=B; if(x<0) x+=B;
ans=(ans+qmul(B/b[i]*a[i],x,B))%B;
}
if(ans<0) ans+=B;
printf("%lld\n", ans);
return 0;
}
但实际上孙子定理还没有完……还得继续仔细看数论讲义
原文：https://www.cnblogs.com/sahdsg/p/10816765.html