这是我的第一篇随笔（其实是为了防止我忘记而做的笔记）
问题引入：
孙子定理是中国古代求解一次同余式组（见 同余）的方法。是 数论中一个重要定理。又称 中国余数定理。一元线性同余方程组问题最早可见于中国 南北朝时期（公元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.然后将这三个数分别乘以对应的余数 152（7为除数所对应的余数）+213（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了吗
貌似没有简单？？
乘法逆元还记得吗？
若ax≡1 mod f, 则称a关于1模f的乘法逆元为x。也可表示为ax≡1(mod f)。
那么就可以这样
逆元可以用扩展欧几里得 费马小定理求解
中国剩余定理给出了以下的一元线性同余方程组：
贴上代码：
#include using namespace std; const int maxn=4e5+7; #define int long long int n; int a[11]; int b[11]; 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=1; int x=0,y=0; for (int i=1;ii)
lcm*=b[i]; for (int j=1;jj)
{ int tmp=lcm/b[j];
_exgcd(tmp,b[j],x,y);///为什么模b[i] 看看上文 x=(x%b[j]+b[j])%b[j];//逆元 ans=(ans+tmp*x*a[j])%lcm;
} return (lcm+ans)%lcm;
}
signed main()
{
cin>>n; for (int i=1;ii)
cin>>b[i]>>a[i];//商 模数 int cnt=china();
coutendl; return 0;
} 过几天补发扩展中国剩余定理
京公网安备 11010502036488号