EXCRT
学习地址：C20182030太强了
博客里面的证明很易懂。
博客里面数论的各个Part都值得一看。
比较简洁的写法：
扩展中国剩余定理：
模数不一定互质，将方程依次合并：
{
x
≡
a
(
m
o
d
b
)
x
≡
c
(
m
o
d
d
)
\begin{cases}x\equiv a~(\bmod~b)\\x\equiv c~(\bmod~d)\end{cases}
{x≡a (mod b)x≡c (mod d)
可知
b
⋅
t
+
a
≡
c
(
m
o
d
d
)
b\cdot t+a\equiv c~(\bmod~d)
b⋅t+a≡c (mod d)
用
exgcd
\text{exgcd}
exgcd求出
t
≡
c
−
a
(
b
,
d
)
∗
(
b
(
b
,
d
)
)
−
1
(
m
o
d
d
(
b
,
d
)
)
t\equiv \frac {c-a}{(b,d)}*(\frac b{(b,d)})^{-1}~(\bmod~\frac {d}{(b,d)})
t≡(b,d)c−a∗((b,d)b)−1 (mod (b,d)d)
代回得
x
≡
b
⋅
t
+
a
(
m
o
d
[
b
,
d
]
)
x\equiv b\cdot t+a~(\bmod~[b,d])
x≡b⋅t+a (mod [b,d])
易验证
x
x
x满足原方程，且方程的通解为
x
+
k
[
b
,
d
]
x+k[b,d]
x+k[b,d]
Code（洛谷P4777）：
#include<bits/stdc++.h>
#define maxn 100005
#define LL long long
using namespace std;
inline LL mul(LL a,LL b,LL p){return (a*b-(LL)((long double)a*b/p)*p+p)%p;}
LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
void exgcd(LL a,LL b,LL &x,LL &y){
if(!b) x=1,y=0;
else exgcd(b,a%b,y,x),y-=a/b*x;
}
int main()
{
int n; LL A1,P1,A2,P2,x,y,d,lcm;
scanf("%d%lld%lld",&n,&P1,&A1);
while(--n){
scanf("%lld%lld",&P2,&A2),d=gcd(P1,P2);
exgcd(P1/d,P2/d,x,y),lcm=P1/d*P2;
A1=(mul(mul((A2-A1)/d,x,lcm),P1,lcm)+A1)%lcm;
P1=lcm;
}
printf("%lld\n",(A1+P1)%P1);
}
EXLUCAS
学习地址：讲的很清楚
求组合数
n
!
m
!
(
n
−
m
)
!
n!\over m!(n-m)!
m!(n−m)!n! 模
p
k
p^k
pk
首先求出上下除去
p
p
p的因子后模
p
k
p^k
pk的值，然后求出下面模
p
k
p^k
pk的逆元。
于是问题就是怎么求
n
!
n!
n!除去
p
p
p的因子后模
p
k
p^k
pk的值。
首先除去
n
!
n!
n!中
p
p
p的倍数，那么被除的数形成了
(
n
p
)
!
(\frac np)!
(pn)!，递归计算。剩下的数不包含
p
p
p的因子，形成了
[
1
,
p
k
)
[1,p^k)
[1,pk)内不包含
p
p
p的因子的这一段的
n
p
k
\frac n{p^k}
pkn次重复，暴力把
[
1
,
p
k
)
[1,p^k)
[1,pk)以内乘起来然后快速幂，剩下的非整段的长度
<
p
k
<p^k
<pk，同样暴力乘起来。
预处理
p
k
p^k
pk以内不含
p
p
p因子的数的前缀积，每次递归就只需要一次快速幂了，总复杂度就是
O
(
p
k
+
log
n
)
O(p^k+\log n)
O(pk+logn)
但是有时候我们会遇到
p
k
p^k
pk和
n
n
n很大，但
m
m
m较小的情况，这时候可以把组合数表示为
n
m
‾
m
!
n^{\underline m}\over m!
m!nm，直接
f
o
r
for
for循环除去
p
p
p的因子，然后剩下的求逆元模就好了。这样复杂度是
O
(
m
log
m
)
O(m\log m)
O(mlogm)的。