这是我的第一篇随笔（其实是为了防止我忘记而做的笔记）
问题引入：
孙子定理是中国古代求解一次同余式组（见同余）的方法。是数论中一个重要定理。又称中国余数定理。一元线性同余方程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下：
有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。
好像还是不太懂 来个百度上的例题
当然一般的做法就是除三余二的数字有2 5 8 11 14 17 20 23....
再从中找出除五余三的数字8 23....
那么在从中找到除七余二的数23
那么最小的数就是23
但我们可以这样
1.找出三个数：从3和5的公倍数中找出被7除余1的最小数15，从3和7的公倍数中找出被5除余1 的最小数21，最后从5和7的公倍数中找出除3余1的最小数70。
2.然后将这三个数分别乘以对应的余数 15*2（7为除数所对应的余数）+21*3（5为除数所对应的余数）+70*2（3为除数对应的余数）=233
3.接下来就是把233-k*lcm（5，3，7） k为任意整数 保持结果为正数即可 所求23即为最小值
为什么要这样求？
假设一下 假设n1%3=2;
n2%5=3 n3%7=2 一个小公式 a%b=c 等价于 (a+b*k)%b=c
所以我们可以看到
n1+n2+n3若要为%3=2 则n2+n3为3的倍数
n1+n2+n3若要为%5=3 则n1+n3为5的倍数
n1+n2+n3若要为%7=2 则n2+n1为7的倍数
所以就可以这样 1.从lcm（3，5）的倍数中找到%7=2的数n3 2.从lcm（3，7）的倍数中找到%5=3的数 n2 3.从lcm（5，7）的倍数中找到%3=2的数 n1
三者相加 减去三者的最小公倍数的k倍即可
注意 ！！！技巧点来了
从lcm（3，5）的倍数中找到%7=2的数n3 枚举吗？
当然不是，我们可以先找到lcm（3，5）的倍数中找到%7=1 的数， 那么直接把该数乘以2， 余数不就为2了吗 譬如7%3=1 14%3==2
貌似没有简单？？
乘法逆元还记得吗？
若ax≡1 mod f, 则称a关于1模f的乘法逆元为x。也可表示为ax≡1(mod f)。
那么就可以这样
逆元可以用扩展欧几里得 费马小定理求
中国剩余定理给出了以下的一元线性同余方程组：
贴上代码
#include <bits/stdc++.h> using namespace std; const int maxn=4e5+7; #define int long long /* 原理：按照顺序，找出满足其他数倍数%当前的值为当前的余数的值 譬如 x=a_1 mod p_1 x=a_2 mod p_2 x=a_3 mod p_3 就是找到一个值，n是p_2 p_3的倍数这样mod _p_2和p_3==0,然后还要满足n mod p_1=a_1 然后一样的操作，每次在满足当前余数的同时mod其他数等于0，这些数相加就满足所有的条件了 但是这样不一定最小，所以最后还要减去所有模数的最小lcm的倍数 这里有一个细节，逆元的定义ax==1 mod p，现在你要mod p_1= a_1 不妨先求出逆元所满足的ax==1 mod p，然后把ax*a_1这样mod就等于a_1了 */ int n; int a[maxn]; int b[maxn]; void _exgcd(int a,int b,int &x,int &y) { if (!b) { x=1; y=0; return ; } _exgcd(b,a%b,x,y); int tmp=x; x=y; y=tmp-(a/b)*y; } int china () { int ans=0; int lcm=1ll; int x=0,y=0; for (int i=1;i<=n;++i) lcm*=b[i];///求出所有数的乘积 for (int j=1;j<=n;++j) { int tmp=lcm/b[j];///除当前数字其他数之积 _exgcd(tmp,b[j],x,y);///既满足其他数值%=0 也满足当前mod=1 x=(x%b[j]+b[j])%b[j];///exgcd_求逆元，保证是最小的正整数，这样的操作相当于把另外一个元减少，加到当前的x ans=(ans%lcm+tmp*x*a[j])%lcm;///n=tmp*x就是当前满足n%b[j]==1,然后*a[j] 所以mod=a[j] } return (lcm+ans%lcm)%lcm;///防止出现负数 } signed main() { cin>>n; for (int i=1;i<=n;++i) cin>>b[i]>>a[i]; int cnt=china(); cout<<cnt<<endl; return 0; }
###声明，由于之前没有处理好图片池，造车博客部分缺失，现已重新修改