数论——中国剩余定理（CRT）
今天也是简简单单学了一下CRT，我感觉这个东西考的不多，其实理解一下，考的时候能记住就OK了，但是还是要理解其中的奥妙
话不多说，先来看中国剩余定理
引例：
有一天，传闻在韩信在井陉之战的时候要去数一下士兵的数量，方便到时候得统一调动，于是乎他让士兵3个一队，发现多出来2个人，让士兵5个人一队，发现多出来三个人，让士兵7个人一队，发现多出来2两个人，问韩信最少的士兵数几何？
答案：23
？？？？就23个韩信这场仗是咋打过对方几十万大军的
中国剩余定理
中国剩余定理的基本思想为：
假如我有一个数x，同时有n个两两互质的数，然后我们知道每个数取模后的剩余的数量，然后要去求这个x最少是多少
x=x1+x2+...+xn；
我们按照上面那个韩信点兵的故事继续讲下去，这样理解会更加深入一点
其求 Xi 结论为：ri*(除了 i 其余模数的乘积）*(除了 i 其余模数的乘积的逆元（取模 第 i 的模数））
然后我们可以求出
x1=2*35*2=140,x2=3*21*1=63,x3=2*15*1=30;
x=233,但是这也不是最终结果23啊？
因为你还没有模上所有模数的乘积
233%105=23；
直接输出即可
拓展中国剩余定理
上面那个中国剩余定理说的是都两两互质的情况才能够运用，但是如果我这n个数并不满足两两互质的情况呢？那我该怎么办？
那就只能用到拓展中国剩余定理了
这样就既可以解决不互质的，也可以解决互质的情况
我们还是假设，有n个数，然后有一个数x，取模这n个数都有对应的余数r
我们在中国剩余定理中可知，假设这个数是ans
ans=lcm(已经出现的数的最小公倍数)*x+tail（所剩下的余数）
还是先假设有三个式子
ans%m1=r1
ans%m2=r2
ans%m3=r3
我们不妨加上一个式子，设初始lcm=1,tail=0
因此我们一开始的ans可以表示任意的整数
我们先去联立第一个取模式子
可以得到
lcm*x+tail=m1*y+r1
我们将其移项得到 lcm*x-m1*y=r1-tail
我们可以发现什么？难道不是那个拓展欧几里得么？ a*x+b*y=gcd(a,b);
但是一个是加，一个是减，这样不一样啊？
肯定是一样的，反正x和y终究都是一个整数，也可以有正负，所以上面那个式子就可以变为
lcm*x+m1*y=r1-tail
因此我们就可以通过拓欧求出x的特解x0，然后找到其通解x0+(m1/gcd(lcm,m1)*k) (k表示任意整数)
然后代入原式，就可以求出ans`可以卡掉一部分情况
ans=lcm*(b/d)*x+lcm*x0+tail
所以每次变化
lcm=lcm*(b/d); (b是每次模的那个数）
tail=(原来的lcm)*x0+tail;
然后运算完所有式子，找到最后的tail就是最终的结果
过程步骤
例题
P1495 【模板】中国剩余定理
这题附加了一个数据，那个数据会爆long long，因此我们需要用龟速乘去处理其中的成法，这样可以避免爆 long long
龟速乘代码：
int mul(int a,int b,int mod)
{int ans=0;while(b>0){if(b%2==1){ans=(ans+a)%mod;}a=(a+a)%mod;b/=2;}return ans;
}AC总代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int a[100005];
int b[100005];
int sum=1;//表示所有数的乘法 int mul(int a,int b,int mod)
{int ans=0;while(b>0){if(b%2==1){ans=(ans+a)%mod;}a=(a+a)%mod;b/=2;}return ans;
}int exgcd(int a,int b,int &x,int &y)
{if(b==0){x=1,y=0;return a;}int x2,y2;int d=exgcd(b,a%b,x2,y2);x=y2;y=x2-a/b*y2;return d;
}signed main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i]>>b[i];sum*=a[i];}int x,y;int ans=0;for(int i=1;i<=n;i++){exgcd(sum/a[i],a[i],x,y);x=(x+a[i])%a[i];int c=mul((mul(b[i],sum/a[i],sum)),x,sum);ans+=c;}cout<<ans%sum;return 0;
}P4777 【模板】扩展中国剩余定理（EXCRT）
就是单纯的拓展中国剩余定理的模版，但是最后一个数据也是会爆long long,我不知道为什么用了龟速乘也会爆，所以，就直接用了__int128_t
然后用上快读和快写就可以过了，感谢学长的做题思路
学长的主页链接
#include<bits/stdc++.h>
using namespace std;
#define int __int128_t
int n;
int a[100005];
int b[100005];int read()
{//直接在函数里面实现读字符串操作更简洁int res=0;//初始结果赋值0char scan[1005];scanf("%s",scan);for(int i=0;i<strlen(scan);i++)res*=10,res+=scan[i]-'0';//实现进位return res;//返回__int128类型
}void print(int num)
{//递归调用，实现从高位向低位输出if(num>9) print(num/10);putchar(num%10+'0');
}int mul(int a,int b,int mod)
{int ans=0;while(b>0){if(b%2==1){ans=(ans+a)%mod;}a=(a+a)%mod;b/=2;}return ans;
}int exgcd(int a,int b,int &x,int &y)
{if(b==0){x=1,y=0;return a;}int x2,y2;int d=exgcd(b,a%b,x2,y2);x=y2;y=x2-a/b*y2;return d;
}signed main()
{n=read();for(int i=1;i<=n;i++){a[i]=read();b[i]=read();}int lcm=1,tail=0;for(int i=1;i<=n;i++){int x,y;int d=exgcd(lcm,a[i],x,y);int c=b[i]-tail;x=c/d*x;//先求出特解 x=(x%(a[i]/d)+(a[i]/d))%(a[i]/d);//通过通解找到最小正整数 int flag=lcm;lcm=lcm*(a[i]/d);tail=(mul(flag,x,lcm)+tail)%lcm;}print(tail%lcm);return 0;
}