同余基本运算：https://www.luogu.com.cn/blog/shenhy1205/tong-yu-ru-men
欧拉： https://www.luogu.com.cn/blog/shenhy1205/ou-la
反演： https://www.luogu.com.cn/blog/shenhy1205/fan-yan-mo-shu
逆元： https://www.luogu.com.cn/blog/shenhy1205/ni-yuan-za-hui
贝祖定理：
对于ax+by=c有解，满足c%gcd(a,b)=0
证明：
设e=gcd(a,b)
a%e=0,b%e=0
ax%e=0,by%e=0
ax+by%e=0
c%e=0
中国剩余定理：求方程组的最小解。
方程组：
{
x≡a1 (mod b1)
x≡a2 (mod b2)
x≡a3 (mod b3)
x≡a4 (mod b4)
…………
x≡ak (mod bk)
}
bi之间两两互质
------------
解：
令M=∏（i,1,k）bi
ti为方程x≡M/bi(mod bi)的最非负小整数解
x=∑(i,1,k)ai * M/bi * ti
通解为x+j*M
最小整数解为 x=(x%M+M)%M
------------
证明：
∵M/bi * ti≡1 (mod bi)
∴ai * M/bi * ti ≡ ai (mod bi)
∵∑(i,1,k)ai * M/bi * ti ≡ ai * M/bi * ti (mod bi)
（除了这组数以外的其他数之和中必然包含bi，因为他们之间两两互质，所以除了这组以外其他组的bi都没被除掉，mod bi =0 只有这组留了下来）
∴x=∑(i,1,k)ai * M/bi * ti 是这方程的解
同理，也是其他方程的解
∴x为整组方程的一个解
代码：
#include <bits/stdc++.h> #define ll long long using namespace std; ll e; void exgcd(ll a,ll b,ll &x,ll &y) { if(!b) x=1,y=0,e=a; else exgcd(b,a%b,y,x),y-=a/b*x; } int n; ll a[11],b[11],t[11],m=1,ans; ll mul(ll x,ll y) { ll s=0; while(y) { if(y&1) s=(s+x)%m; x=2*x%m; y>>=1; } return s%m; } void china() { for(int i=1;i<=n;i++) { ll y; exgcd(m/b[i],b[i],t[i],y); t[i]=(t[i]%b[i]+b[i])%b[i]; ans=(ans+mul(mul(a[i],m/b[i]),t[i]))%m; } } int main() { cin>>n; for(int i=1;i<=n;i++) scanf("%lld",a+i); for(int i=1;i<=n;i++) scanf("%lld",b+i),m*=b[i]; china(); printf("%lld ",ans); return 0; }
扩展欧几里得：
对于ax+by=c求解
首先考虑对于:
ax+by=gcd(a,b)
bx0+(a%b)y0=gcd(b,a%b)
bx0+(a-a/b*b)y0=gcd(b,a%b)
ay0+b(x0-a/b*y0)=gcd(b,a%b)
联立ax+by =gcd(a,b)
x=y0,y=x0-a/b*y0
一直递归
直到gcd边界
于是，我们就得到了一组解
如果c%e！=0，那么根据贝祖定理，方程无解
将得到的x1=x*c/gcd(a,b),y1=y*c/gcd(a,b)就是ax+by=c的解
同时，我们发现当x每改变b/gcd(a,b)时，总有一个y能让等式成立（改变a/gcd(a,b)）
d=a/gcd(a,b),e=b/gcd(a,b)
有最小解：x2=(x1%d+d)%d,y2=(y1%d+d)%d
有通解：x2+ke,y+kd (k为整数)
代码：
void exgcd(ll a,ll b,ll &x,ll &y) { if(!b) x=1,y=0,e=a; else exgcd(b,a%b,y,x),y-=a/b*x; }