前置知识
初等数论，简单数学知识。
群论
很多数论知识都需要群论证明，我们先简单了解一下群论。
设 GGG 为一个非空集合，定义运算 ⋅\cdot⋅，(G,⋅)(G,\cdot)(G,⋅) 为一个群当且仅当：
1. 封闭性：∀a,b∈G,a⋅b∈G\forall a,b \in G,a \cdot b \in G∀a,b∈G,a⋅b∈G。
2. 结合律：∀a,b,c∈G,(a⋅b)⋅c=a⋅(b⋅c)\forall a,b,c \in G,(a \cdot b) \cdot c=a \cdot (b \cdot c)∀a,b,c∈G,(a⋅b)⋅c=a⋅(b⋅c)。
3. 单位元：∃e∈G,∀a∈G,e⋅a=a⋅e=a\exist e \in G,\forall a \in G,e \cdot a=a \cdot e=a∃e∈G,∀a∈G,e⋅a=a⋅e=a。
4. 逆元：∀a∈G,∃b∈G,a⋅b=b⋅a=e\forall a \in G,\exist b \in G,a \cdot b=b \cdot a=e∀a∈G,∃b∈G,a⋅b=b⋅a=e，记作 b=a−1b=a^{-1}b=a−1。
如果一个群 GGG 的元素数量是有限的，那么它就是有限群，它的元素数量叫做它的阶，记作 ∣G∣\lvert G\rvert∣G∣。
对于有限群 GGG，如果 H⊆GH \subseteq GH⊆G，并且 G,HG,HG,H 的运算相同，则称 HHH 为 GGG 的子群。
对于 a∈Ga \in Ga∈G，使 ak=ea^k=eak=e 成立的最小正整数 kkk 称作 aaa 的阶，记作 ord(a)\operatorname{ord}(a)ord(a)。
拉格朗日定理
对于有限群 GGG，若 HHH 为 GGG 的子群，则 ∣H∣∣∣G∣\lvert H\rvert \mid \lvert G\rvert∣H∣∣∣G∣，即 HHH 的阶整除 GGG 的阶。
> 以下证明中的 ⋅\cdot⋅ 运算符号省略。
>
> ∀a∈G\forall a \in G∀a∈G，定义左陪集：
>
> aH={ah∣h∈H}aH=\left\{ah \mid h\in H\right\} aH={ah∣h∈H}
>
> aHaHaH 的元素与 HHH 一一对应，因此 ∣aH∣=∣H∣\lvert aH\rvert=\lvert H\rvert∣aH∣=∣H∣。
>
> 取两个不同的陪集 aH,bHaH,bHaH,bH，假设它们有公共元素，即 ∃h1,h2∈H,ah1=bh2\exist h_1,h_2 \in H,ah_1=bh_2∃h1 ,h2 ∈H,ah1 =bh2 ，则 a=bh2h1−1a=b h_2h_1^{-1}a=bh2 h1−1 。
>
> 又因为 h2h1−1∈Hh_2h_1^{-1}\in Hh2 h1−1 ∈H，所以 a∈bHa\in bHa∈bH。
>
> ∀ah∈aH,ah=(bh2h1−1)h=b(h2h1−1h)∈bH\forall ah \in aH,ah=(bh_2h_1^{-1})h=b(h_2h_1^{-1}h)\in bH∀ah∈aH,ah=(bh2 h1−1 )h=b(h2 h1−1 h)∈bH，所以 aH⊆bHaH \subseteq bHaH⊆bH。
>
> 同理可证：bH⊆aHbH\subseteq aHbH⊆aH，因此 aH=bHaH = bHaH=bH。与假设“不同的陪集”矛盾，因此 aH,bHaH,bHaH,bH 不存在公共元素。
>
> 设不同的陪集有 kkk 个，可得：∣G∣=k∣H∣\lvert G\rvert=k\lvert H\rvert∣G∣=k∣H∣。即 ∣H∣∣∣G∣\lvert H\rvert \mid \lvert G\rvert∣H∣∣∣G∣。
推论：设 ∣G∣=m\lvert G \rvert=m∣G∣=m，∀a∈G,am=e\forall a \in G,a^m=e∀a∈G,am=e。
> 取 aaa 生成的循环子群 ⟨a⟩={ax∣x∈N}\langle a\rangle=\left\{a^x \mid x\in \mathbb{N}\right\}⟨a⟩={ax∣x∈N}，容易知道其阶等于 aaa 的阶，且为 GGG 的子群。由拉格朗日定理得：ord(a)∣m\operatorname{ord}(a) \mid mord(a)∣m。因此：
>
> am=(aord(a))mord(a)=emord(a)=ea^m=(a^{\operatorname{ord}(a)})^{\frac{m}{\operatorname{ord}(a)}}=e^{\frac{m}{\operatorname{ord}(a)}}=e am=(aord(a))ord(a)m =eord(a)m =e
费马小定理
若 ppp 为素数，且 p∤ap \nmid ap∤a，则：
ap−1≡1(modp)a^{p-1}\equiv1\pmod p ap−1≡1(modp)
> 令 G=(Z/pZ)×G=(\mathbb{Z}/p\mathbb{Z})^\timesG=(Z/pZ)×（即所有与 ppp 互质的剩余类），易知 ∣G∣=p−1\lvert G\rvert=p-1∣G∣=p−1。
>
> 因为 p∤ap \nmid ap∤a，所以 a∈Ga \in Ga∈G，根据拉格朗日定理的推论，a∣G∣=ea^{\lvert G\rvert}=ea∣G∣=e，即 ap−1≡1(modp)a^{p-1}\equiv 1\pmod pap−1≡1(modp)。
欧拉定理
若 gcd(a,n)=1\gcd(a,n)=1gcd(a,n)=1，则：
aφ(n)≡1(modn)a^{\varphi(n)}\equiv 1\pmod n aφ(n)≡1(modn)
> 令 G=(Z/nZ)×G=(\mathbb{Z}/n\mathbb{Z})^\timesG=(Z/nZ)×，易知 ∣G∣=φ(n)\lvert G\rvert=\varphi(n)∣G∣=φ(n)。
>
> 因为 gcd(a,n)=1\gcd(a,n)=1gcd(a,n)=1，所以 a∈Ga \in Ga∈G，a∣G∣=ea^{\lvert G\rvert}=ea∣G∣=e，即 aφ(n)≡1(modn)a^{\varphi(n)}\equiv 1\pmod naφ(n)≡1(modn)。
扩展欧拉定理
ab≡{ab mod φ(p)gcd(a,p)=1abgcd(a,p)≠1,b<φ(p)a(b mod φ(p))+φ(p)gcd(a,p)≠1,b≥φ(p)(modp)a^b \equiv \begin{cases} a^{b\ \bmod\ \varphi(p)} & \gcd(a,p)=1 \\ a^b & \gcd(a,p) \neq 1,b<\varphi(p) \\ a^{(b\ \bmod\ \varphi(p))+\varphi(p)} & \gcd(a,p) \neq 1,b \geq \varphi(p) \end{cases} \pmod p ab≡⎩⎨⎧
ab mod φ(p)aba(b mod φ(p))+φ(p) gcd(a,p)=1gcd(a,p)=1,b<φ(p)gcd(a,p)=1,b≥φ(p) (modp)
ppp 不一定是质数。
> 第一项就是欧拉定理，当 gcd(a,p)≠1\gcd(a,p) \neq 1gcd(a,p)=1 的时候，把 ppp 质因数分解，对于每一个 pkp^kpk 证明原式成立，然后用 CRT 合并（CRT 见后文）即可。懒得证了。
裴蜀定理
若 a,b,ca,b,ca,b,c 均为整数，ax+by=cax+by=cax+by=c 存在整数解 (x,y)(x,y)(x,y) 当且仅当 gcd(a,b)∣c\gcd(a,b) \mid cgcd(a,b)∣c。
> 设 S={ax+by∣x,y∈Z,ax+by>0}S=\left\{ax+by \mid x,y \in \mathbb{Z},ax+by>0\right\}S={ax+by∣x,y∈Z,ax+by>0}，易知 SSS 为 N+\mathbb{N^+}N+ 的非空子集。设 SSS 中元素的最小值为 ***。容易知道必然存在整数 x,yx,yx,y 使得 d=ax+byd=ax+byd=ax+by。
>
> 可以知道存在整数 q,rq,rq,r 满足 a=qd+ra=qd+ra=qd+r，其中 0≤r<d0 \leq r<d0≤r<d。
>
> 把 *** 带入：r=a−qd=a−q(ax+by)=a(1−qx)+b(−qy)r=a-qd=a-q(ax+by)=a(1-qx)+b(-qy)r=a−qd=a−q(ax+by)=a(1−qx)+b(−qy)。
>
> 如果 r>0r>0r>0，那么 r∈Sr \in Sr∈S 并且 r<dr<dr<d，矛盾，因此 r=0r=0r=0，即 d∣ad \mid ad∣a。
>
> 同理，可证：d∣bd \mid bd∣b。因此 *** 为 a,ba,ba,b 的公因数。
>
> 设 kkk 是 a,ba,ba,b 的一个公因数，可得 k∣dk \mid dk∣d，即 k≤dk \leq dk≤d，因此 *** 为 a,ba,ba,b 的最大公因数，即 d=gcd(a,b)d=\gcd(a,b)d=gcd(a,b)。
>
> 设 m=cgcd(a,b)m=\frac{c}{\gcd(a,b)}m=gcd(a,b)c ，显然把 x,yx,yx,y 均乘上 mmm 就可以得到 ax+by=cax+by=cax+by=c 的解，所以 gcd(a,b)∣c\gcd(a,b) \mid cgcd(a,b)∣c 的充分性得证；
>
> 因为 d=gcd(a,b)d=\gcd(a,b)d=gcd(a,b)，所以 d∣(ax+by)d \mid (ax+by)d∣(ax+by)，即 d∣cd \mid cd∣c，gcd(a,b)∣c\gcd(a,b) \mid cgcd(a,b)∣c 的必要性得证。
>
> 所以，gcd(a,b)∣c\gcd(a,b)\mid cgcd(a,b)∣c 是存在整数解的充要条件。
扩展欧几里得算法（EXGCD）
求 ax+by=gcd(a,b)ax+by=\gcd(a,b)ax+by=gcd(a,b) 的一组特解。
由裴蜀定理容易知道一定有解。
如果 b=0b=0b=0，gcd(a,b)=a\gcd(a,b)=agcd(a,b)=a，此时 x=1,y=0x=1,y=0x=1,y=0。
考虑 aaa 除以 bbb，设 a=qb+ra=qb+ra=qb+r，其中 0≤r<b0 \leq r<b0≤r<b。可以推出 gcd(a,b)=gcd(b,a mod b)=gcd(b,r)\gcd(a,b)=\gcd(b,a\bmod b)=\gcd(b,r)gcd(a,b)=gcd(b,amodb)=gcd(b,r)。
设 gcd(b,r)\gcd(b,r)gcd(b,r) 这一步返回了 x0,y0x_0,y_0x0 ,y0 ，得到：
bx0+ry0=gcd(a,b)bx0+(a−qb)y0=gcd(a,b)ay0+b(x0−qy0)=gcd(a,b)bx_0+ry_0=\gcd(a,b) \\ bx_0+(a-qb)y_0=\gcd(a,b) \\ ay_0+b(x_0-qy_0)=\gcd(a,b) bx0 +ry0 =gcd(a,b)bx0 +(a−qb)y0 =gcd(a,b)ay0 +b(x0 −qy0 )=gcd(a,b)
其中 q=⌊ab⌋q=\lfloor \frac{a}{b} \rfloorq=⌊ba ⌋。
显然我们可以令：
x1=y0,y1=x0−⌊ab⌋y0x_1=y_0,y_1=x_0-\lfloor \frac{a}{b}\rfloor y_0 x1 =y0 ,y1 =x0 −⌊ba ⌋y0
显然第一步是正确的，后面每一步是由前一步推导出的，所以也都是正确的。
这就是扩展欧几里得算法的流程。
时间复杂度：O(log(a+b))O(\log (a+b))O(log(a+b))。
扩展中国剩余定理（EXCRT）
普通 CRT 感觉不如 exCRT，不讲了。
给定 ai,mia_i,m_iai ,mi ，解同余方程：
{x≡a1(modm1)⋯x≡an(modmn)\begin{cases} x \equiv a_1 \pmod{m_1} \\ \cdots \\ x \equiv a_n \pmod{m_n} \end{cases} ⎩⎨⎧ x≡a1 (modm1 )⋯x≡an (modmn )
mim_imi 不一定两两互质。
考虑两两合并，对于 x≡a1(modm1)x \equiv a_1\pmod{m_1}x≡a1 (modm1 ) 与 x≡a2(modm2)x\equiv a_2\pmod{m_2}x≡a2 (modm2 )。
这等价于：x=a1+y1m1x=a_1+y_1m_1x=a1 +y1 m1 与 x=a2+y2m2x=a_2+y_2m_2x=a2 +y2 m2 。带入：a1+y1m1=a2+y2m2a_1+y_1m_1=a_2+y_2m_2a1 +y1 m1 =a2 +y2 m2 ，即 m1y1−m2y2=a2−a1m_1y_1-m_2y_2=a_2-a_1m1 y1 −m2 y2 =a2 −a1 ，利用扩展欧几里得算法算出一组 (y1,y2)(y_1,y_2)(y1 ,y2 )，算不出来说明整个同余方程无解，算出来了就可以得到 x≡a1+y1m1(modlcm(m1,m2))x\equiv
a_1+y_1m_1\pmod{\operatorname{lcm}(m_1,m_2)}x≡a1 +y1 m1 (modlcm(m1 ,m2 ))。
时间复杂度：O(nlogM)O(n \log M)O(nlogM)。
大步小步算法（BSGS）
解方程：ax≡b(modp)a^x \equiv b \pmod pax≡b(modp)，a,pa,pa,p 互质。
设 m=⌈p⌉m=\lceil \sqrt{p}\rceilm=⌈p ⌉，得到 x=im+jx=im+jx=im+j，其中 0≤i<m,0≤j<m0 \leq i<m,0 \leq j<m0≤i<m,0≤j<m。
带入：
aim+j=baj=b(a−m)ia^{im+j}=b \\ a^j=b(a^{-m})^i aim+j=baj=b(a−m)i
枚举 jjj，计算 gj mod pg^j \bmod pgjmodp 记下来，然后枚举 iii，计算 t=b(a−m)i(modp)t=b(a^{-m})^i \pmod pt=b(a−m)i(modp)，查找 ttt，找到了就说明此时的 xxx 是解。如果最终都没找到，说明无解。
时间复杂度：O(p)O(\sqrt{p})O(p )。
扩展大步小步算法（EXBSGS）
解方程：ax≡b(modp)a^x \equiv b\pmod{p}ax≡b(modp)，a,pa,pa,p 不一定互质。
首先把 a,ba,ba,b 取模，特判 p=1p=1p=1 或 b=1b=1b=1 的情况。
我们计算 d=gcd(a,p)d=\gcd(a,p)d=gcd(a,p)，如果 b mod d≠0b \bmod d \neq 0bmodd=0，则无解。否则我们可以得到：adax−1≡bd(modpd)\frac{a}{d}a^{x-1}\equiv\frac{b}{d}\pmod{\frac{p}{d}}da ax−1≡db (moddp )。
令：
b←bdp←pdb \leftarrow \frac{b}{d} \\ p \leftarrow\frac{p}{d} b←db p←dp
不断进行上面的操作，直到 a,pa,pa,p 互质。设我们进行了 kkk 次操作，mmm 表示每一轮的 ad\frac{a}{d}da 的乘积，则我们得到了：
max−k≡b(modp)ax−k≡bm−1(modp)ma^{x-k}\equiv b\pmod p \\ a^{x-k}\equiv bm^{-1}\pmod p max−k≡b(modp)ax−k≡bm−1(modp)
此时 a,pa,pa,p 互质，跑 BSGS 即可。
但是还有一种可能，就是答案 x<kx<kx<k，所以在每次计算 d=gcd(a,p)d=\gcd(a,p)d=gcd(a,p) 之前枚举 x=0,1,…,k−1x=0,1,\dots,k-1x=0,1,…,k−1 就好。
时间复杂度：O(p)O(\sqrt{p})O(p )。
LUCAS 定理
设 ppp 为质数，则：
(nm)≡(⌊np⌋⌊mp⌋)(n mod pm mod p)(modp)\binom{n}{m}\equiv\binom{\lfloor\frac{n}{p}\rfloor}{\lfloor\frac{m}{p}\rfloor}\binom{n\bmod p}{m\bmod p}\pmod p (mn )≡(⌊pm ⌋⌊pn ⌋ )(mmodpnmodp )(modp)
> 考虑组合意义，设 n=qp+r,m=sp+tn=qp+r,m=sp+tn=qp+r,m=sp+t，0≤r<p,0≤t<p0\leq r<p,0 \leq t<p0≤r<p,0≤t<p，将 nnn 个球排成一圈，每 qqq 个分成一组，每组 ppp 个球，最终剩下 rrr 个球没有组。设这 qqq 组为 G1,G2,…,GqG_1,G_2,\dots,G_qG1 ,G2 ,…,Gq ，没有组的为 G0G_0G0 。
>
> 考虑从 nnn 个球中选出 mmm 个，设在 GiG_iGi 中选了 kik_iki 个球（1≤i≤q,0≤ki≤p,0≤k0≤r1 \leq i \leq q,0 \leq k_i \leq p,0 \leq k_0 \leq r1≤i≤q,0≤ki ≤p,0≤k0 ≤r），则 ∑ki+k0=m\sum k_i+k_0=m∑ki +k0 =m，总方案数为：
>
> (nm)≡(rk0)∏i=1q(pki)(modp)\binom{n}{m}\equiv\binom{r}{k_0}\prod_{i=1}^q\binom{p}{k_i}\pmod p (mn )≡(k0 r )i=1∏q (ki p )(modp)
>
> 假设 ∃1≤i≤q,1≤ki≤p−1\exist 1 \leq i \leq q,1 \leq k_i \leq p-1∃1≤i≤q,1≤ki ≤p−1，那么有 (pki)≡0(modp)\binom{p}{k_i}\equiv0\pmod p(ki p )≡0(modp)，因此在总方案数中，它们没有贡献，我们只需考虑 ki=0k_i=0ki =0 或 ki=pk_i=pki =p 的部分产生的贡献。又因为 m=sp+tm=sp+tm=sp+t，所以一共有 sss 个 ki=pk_i=pki =p，而 k0=tk_0=tk0 =t。所以总方案数为：
>
> (qs)(rt)\binom{q}{s}\binom{r}{t} (sq )(tr )
>
> 因此：
>
> (nm)≡(⌊np⌋⌊mp⌋)(n mod pm mod p)(modp)\binom{n}{m}\equiv\binom{\lfloor\frac{n}{p}\rfloor}{\lfloor\frac{m}{p}\rfloor}\binom{n\bmod p}{m\bmod p}\pmod p (mn )≡(⌊pm ⌋⌊pn ⌋ )(mmodpnmodp )(modp)
扩展 LUCAS 定理（EXLUCAS）
计算
(nm) mod p\binom{n}{m} \bmod p (mn )modp
其中 ppp 不一定是质数。
我们考虑把 ppp 质因数分解，对于每一个 pkp^kpk 分别求解，最后用 CRT 或 exCRT 合并。
设 f(n)f(n)f(n) 表示在 n!n!n! 中，含有多少个质因子 ppp。容易知道：
f(n)=∑i=1∞⌊npi⌋=⌊np⌋+f(⌊np⌋)f(n)=\sum_{i=1}^\infin \lfloor\frac{n}{p^i}\rfloor=\lfloor\frac{n}{p}\rfloor+f(\lfloor \frac{n}{p}\rfloor) f(n)=i=1∑∞ ⌊pin ⌋=⌊pn ⌋+f(⌊pn ⌋)
那么 (nm)\binom{n}{m}(mn ) 中包含的质因子 ppp 的数量 c=f(n)−f(m)−f(n−m)c=f(n)-f(m)-f(n-m)c=f(n)−f(m)−f(n−m)。
设 g(n)g(n)g(n) 表示在 n!n!n! 中，除以所有的 ppp 之后剩下的数对 pkp^kpk 取模结果。即：
g(n)=n!pf(n) mod pkg(n)=\frac{n!}{p^{f(n)}} \bmod p^k g(n)=pf(n)n! modpk
推一些式子：
n!=(∏1≤i≤n,p∤ii)(∏i=1⌊np⌋i⋅p)=(∏1≤i≤n,p∤ii)p⌊np⌋(⌊np⌋!)n!=\left(\prod_{1 \leq i \leq n,p \nmid i} i\right)\left(\prod_{i=1}^{\lfloor\frac{n}{p}\rfloor}i\cdot p\right) \\ =\left(\prod_{1\leq i\leq n,p \nmid i}i\right)p^{\lfloor\frac{n}{p}\rfloor}\left(\lfloor\frac{n}{p}\rfloor!\right) n!= 1≤i≤n,p∤i∏
i i=1∏⌊pn ⌋ i⋅p = 1≤i≤n,p∤i∏ i p⌊pn ⌋(⌊pn ⌋!)
两边同时除以 pf(n)p^{f(n)}pf(n)：
g(n)=(∏1≤i≤n,p∤ii)g(⌊np⌋)g(n)=\left(\prod_{1\leq i\leq n,p \nmid i}i\right)g\left(\lfloor\frac{n}{p}\rfloor\right) g(n)= 1≤i≤n,p∤i∏ i g(⌊pn ⌋)
其中 g(0)=1g(0)=1g(0)=1。
考虑快速计算 ∏1≤i≤n,p∤ii\prod_{1\leq i\leq n,p \nmid i}i∏1≤i≤n,p∤i i，我们知道，x≡x+pk(modpk)x\equiv x+p^k \pmod{p^k}x≡x+pk(modpk)，因此我们可以仅仅计算从 111 到 npk\frac{n}{p^k}pkn 部分中，不被 ppp 整除的数的乘积。对其求前缀积 h(n)h(n)h(n) 可得：
(∏1≤i≤n,p∤ii)≡h(pk)⌊npk⌋h(n mod (pk))(modpk)\left(\prod_{1\leq i\leq n,p \nmid i}i\right)\equiv h\left(p^k\right)^{\lfloor\frac{n}{p^k}\rfloor}h\left(n \bmod \left(p^k\right)\right) \pmod{p^k} 1≤i≤n,p∤i∏ i ≡h(pk)⌊pkn ⌋h(nmod(pk))(modpk)
综合起来：
(nm)≡pcg(n)g(m)−1g(n−m)−1(modpk)\binom{n}{m}\equiv p^cg(n)g(m)^{-1}g(n-m)^{-1} \pmod{p^k} (mn )≡pcg(n)g(m)−1g(n−m)−1(modpk)
然后 CRT 或 exCRT 合并，于是就做完了。时间复杂度：O(p)O(p)O(p)。
整除分块
求：
∑i=1n⌊ni⌋\sum_{i=1}^n \lfloor\frac{n}{i}\rfloor i=1∑n ⌊in ⌋
性质：⌊ni⌋\lfloor\frac{n}{i}\rfloor⌊in ⌋ 取值只有 O(n)O(\sqrt{n})O(n ) 种。
> 当 i≤ni \leq \sqrt{n}i≤n ，iii 的取值最多 n\sqrt{n}n 个，因此原式取值最多 n\sqrt{n}n 个。
>
> 当 i>ni>\sqrt{n}i>n ，⌊ni⌋<n\lfloor\frac{n}{i}\rfloor<\sqrt{n}⌊in ⌋<n ，取值最多 n\sqrt{n}n 个。
显然每种取值也是连续的。所以我们考虑对于每一段计算。
设当前段左端点为 lll，右端点为 rrr，那么这一段的值为 v=⌊nl⌋v=\lfloor\frac{n}{l}\rfloorv=⌊ln ⌋，rrr 为满足 ⌊nr⌋=v\lfloor\frac{n}{r}\rfloor=v⌊rn ⌋=v 的最大整数。
有如下式子：
v≤nr<v+1r≤⌊nl⌋v\leq\frac{n}{r}<v+1 \\ r \leq \lfloor\frac{n}{l}\rfloor v≤rn <v+1r≤⌊ln ⌋
因此 r=⌊n⌊nl⌋⌋r=\lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\rfloorr=⌊⌊ln ⌋n ⌋。
时间复杂度：O(n)O(\sqrt{n})O(n )。
如果所求式子带权：
∑i=1nf(i)⌊ni⌋\sum_{i=1}^n f(i)\lfloor\frac{n}{i}\rfloor i=1∑n f(i)⌊in ⌋
处理 fff 的前缀和，每一段乘上 fff 的区间和即可。
如果是二维整除分块：
∑i=1min(n,m)⌊ni⌋⌊mi⌋\sum_{i=1}^{\min(n,m)}\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor i=1∑min(n,m) ⌊in ⌋⌊im ⌋
其他部分不变，只考虑 rrr 怎么求。类似上面的式子推一下就能得到：r=min(⌊n⌊nl⌋⌋,⌊m⌊ml⌋⌋)r=\min\left(\lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\rfloor,\lfloor\frac{m}{\lfloor\frac{m}{l}\rfloor}\rfloor\right)r=min(⌊⌊ln ⌋n ⌋,⌊⌊lm ⌋m ⌋)。
kkk 维类似。时间复杂度 O(kn)O(k\sqrt{n})O(kn )。
莫比乌斯反演
μ(n)={1n=1(−1)kn=p1p2p3…pk,∀1≤i≤k,pi∈P,∀1≤i<j≤k,pi≠pj0∃p∈P,p2∣n\mu(n)=\begin{cases}1&n=1\\(-1)^k&n=p_1p_2p_3\dots p_k,\forall 1 \leq i \leq k,p_i\in\mathbb{P},\forall 1 \leq i<j \leq k,p_i \neq p_j \\0 & \exist p \in \mathbb{P},p^2 \mid n\end{cases} μ(n)=⎩⎨⎧ 1(−1)k0 n=1n=p1 p2 p3 …pk ,∀1≤i≤k,pi
∈P,∀1≤i<j≤k,pi =pj ∃p∈P,p2∣n
意思就是，如果 n=1n=1n=1，那么 μ(n)=1\mu(n)=1μ(n)=1；如果 nnn 的质因数分解中有 kkk 个质因子，并且指数都为 111，那么 μ(n)=(−1)k\mu(n)=(-1)^kμ(n)=(−1)k；否则 μ(n)=0\mu(n)=0μ(n)=0。
性质：
∑d∣nμ(d)={1n=10n≠1\sum_{d \mid n}\mu(d)=\begin{cases}1&n=1\\0&n\neq1\end{cases} d∣n∑ μ(d)={10 n=1n=1
> 首先第一项是显然的，我们证明第二项。
>
> 容易发现形如 ∏i=1kpi\prod_{i=1}^k p_i∏i=1k pi 形式的 ddd 才是有贡献的。设 nnn 有 kkk 个不同的质因子，我们从中选取若干个组成了 ddd。如果选取了偶数个，则 μ(d)=1\mu(d)=1μ(d)=1，如果选取了奇数个，则 μ(d)=−1\mu(d)=-1μ(d)=−1。
>
> 设这 kkk 个不同的质因子中有一个特殊质因子 ppp。我们先在其他 k−1k-1k−1 个质因子中选取，最后决定选不选 ppp。显然，最后选 ppp 的方案数与不选 ppp 的方案数相同，但是对于同一种选取其他质因子的方案，选不选 ppp 之后的集合大小奇偶性不同。因此，选取偶数个的方案数等于选取奇数个的方案数。也就是 ∑d∣nμ(d)=0 (n≠1)\sum_{d \mid n}\mu(d)=0\ (n\neq1)∑d∣n μ(d)=0 (n=1)。
假设我们已知：
f(n)=∑n∣dg(d)f(n)=\sum_{n \mid d} g(d) f(n)=n∣d∑ g(d)
那么根据反演有：
g(n)=∑n∣dμ(dn)f(d)g(n)=\sum_{n\mid d}\mu\left(\frac{d}{n}\right)f(d) g(n)=n∣d∑ μ(nd )f(d)
> ∑n∣dμ(dn)f(d)=∑n∣dμ(dn)∑d∣kg(k)\sum_{n\mid d}\mu\left(\frac{d}{n}\right)f(d)=\sum_{n \mid d}\mu\left(\frac{d}{n}\right)\sum_{d \mid k}g(k) n∣d∑ μ(nd )f(d)=n∣d∑ μ(nd )d∣k∑ g(k)
>
> 令 t=dnt=\frac{d}{n}t=nd ，有：
>
> ∑n∣dμ(dn)∑d∣kg(k)=∑n∣kg(k)∑t∣knμ(t)=∑n∣kg(k)[kn=1]=g(n)\sum_{n \mid d}\mu\left(\frac{d}{n}\right)\sum_{d \mid k}g(k)=\sum_{n \mid k}g(k)\sum_{t \mid \frac{k}{n}} \mu(t)=\sum_{n\mid k}g(k)\left[\frac{k}{n}=1\right]=g(n) n∣d∑ μ(nd )d∣k∑ g(k)=n∣k∑ g(k)t∣nk ∑ μ(t)=n∣k∑ g(k)[nk =1]=g(n)
>
> 得证。
μ(n)\mu(n)μ(n) 一般使用线性筛求出，代码如下：
例题
P5091 【模板】扩展欧拉定理
> 求 ab mod ma^b \bmod mabmodm，1≤a≤109,1≤b≤1020000000,1≤m≤1081 \leq a\leq 10^9,1 \leq b \leq 10^{20000000},1 \leq m \leq 10^81≤a≤109,1≤b≤1020000000,1≤m≤108。
模板不讲了。
代码：
P5656 【模板】二元一次不定方程 (EXGCD)
> 给定不定方程 ax+by=cax+by=cax+by=c，无解输出 −1-1−1；有正整数解输出正整数解数量，正整数解中 xxx 的最小值、最大值，正整数解中 yyy 的最小值、最大值；无正整数解有整数解输出整数解中 xxx 的最小正整数值，yyy 的最小正整数值。
判无解用裴蜀定理，求特解 x0,y0x_0,y_0x0 ,y0 使用 exgcd，考虑推出通解形式。有：
a(x0+db)+b(y0−da)=ca(x_0+db)+b(y_0-da)=c a(x0 +db)+b(y0 −da)=c
其中 db,dadb,dadb,da 为整数。所以，最小的 d=1gcd(a,b)d=\frac{1}{\gcd(a,b)}d=gcd(a,b)1 。令 d1=bgcd(a,b),d2=agcd(a,b)d_1=\frac{b}{\gcd(a,b)},d_2=\frac{a}{\gcd(a,b)}d1 =gcd(a,b)b ,d2 =gcd(a,b)a ，sss 为整数，有通解：
x=x0+sd1,y=y0−sd2x=x_0+sd_1, y=y_0-sd_2 x=x0 +sd1 ,y=y0 −sd2
当 xxx 为正整数时，有 x>0x>0x>0，即：
x0+sd1>0→s>−x0d1x_0+sd_1>0 \rightarrow s>-\frac{x_0}{d_1} x0 +sd1 >0→s>−d1 x0
当 yyy 为正整数时，有 y>0y>0y>0，即：
y0−sd2>0→s<y0d2y_0-sd_2>0 \rightarrow s<\frac{y_0}{d_2} y0 −sd2 >0→s<d2 y0
分类讨论即可。
代码：
P4774 [NOI2018] 屠龙勇士
> 有 nnn 条龙，mmm 把剑，你需要按顺序屠龙。每次屠龙，你需要选择攻击力不高于龙血量 aia_iai 的一把攻击力最高的剑，如果没有选取攻击力最低的，并攻击龙 xxx 次。设本次攻击力为 bib_ibi ，则你需要满足 bix≡ai(modpi)b_ix \equiv a_i\pmod{p_i}bi x≡ai (modpi )，并且 bix≥aib_ix\geq a_ibi x≥ai 。击败这只龙之后你会获得一把新的剑，旧的剑消失。求最小的正整数 xxx 或者报告无解。
我们先不考虑这个同余式和不等式，思考应该怎么选剑。显然，我们可以用一个 multiset 和二分查找完成。这样我们就确定了每一个 bib_ibi 。然后我们跑一个 exCRT 求出最小的 xxx，再利用通解公式求出满足不等式的最小解即可。
简单说一下怎么求通解。设 P=lcmi=1n(pi)P=\operatorname{lcm}_{i=1}^n(p_i)P=lcmi=1n (pi )，我们求出来的解为 x0x_0x0 ，则有：
x0≡C(modP)x≡C(modP)x_0\equiv C\pmod P \\ x\equiv C\pmod P x0 ≡C(modP)x≡C(modP)
求出 CCC，可以得到：x=sP+Cx=sP+Cx=sP+C，其中 sss 为整数。假设不等式的解集为 x≥Tx \geq Tx≥T，则 sP+C≥TsP+C \geq TsP+C≥T，s≥⌈T−CP⌉s \geq \lceil\frac{T-C}{P}\rceils≥⌈PT−C ⌉，答案即为 ⌈T−CP⌉P+C\lceil\frac{T-C}{P}\rceil P+C⌈PT−C ⌉P+C。
代码：
P4345 [SHOI2015] 超能粒子炮·改
> 求：
>
> ∑i=0k(ni) mod 2333\sum_{i=0}^k \binom{n}{i} \bmod 2333 i=0∑k (in )mod2333
设 p=2333p=2333p=2333，再设函数 fff：
f(n,k)=∑i=0k(ni) mod p=∑i=0k(⌊np⌋⌊ip⌋)(n mod pi mod p) mod p=(∑i=0⌊kp⌋−1(⌊np⌋i)(∑j=0p−1(n mod pj))+(⌊np⌋⌊kp⌋)(∑j=0k mod p(n mod pj))) mod p=(2n mod p∑i=0⌊kp⌋−1(⌊np⌋i)+(⌊np⌋⌊kp⌋)(∑j=0k mod p(n mod pj))) mod p=(2n mod pf(⌊np⌋,⌊kp⌋−1)+(⌊np⌋⌊kp⌋)(∑j=0k mod p(n mod pj))) mod pf(n,k)=\sum_{i=0}^k
\binom{n}{i} \bmod p \\ =\sum_{i=0}^k \binom{\lfloor\frac{n}{p}\rfloor}{\lfloor\frac{i}{p}\rfloor}\binom{n \bmod p}{i \bmod p}\bmod p \\ =\left(\sum_{i=0}^{\left\lfloor\frac{k}{p}\right\rfloor-1}\binom{\lfloor\frac{n}{p}\rfloor}{i}\left(\sum_{j=0}^{p-1}\binom{n \bmod
p}{j}\right)+\binom{\lfloor\frac{n}{p}\rfloor}{\lfloor\frac{k}{p}\rfloor}\left(\sum_{j=0}^{k\ \bmod\ p}\binom{n \bmod p}{j}\right)\right) \bmod p \\ =\left(2^{n\ \bmod\
p}\sum_{i=0}^{\left\lfloor\frac{k}{p}\right\rfloor-1}\binom{\lfloor\frac{n}{p}\rfloor}{i}+\binom{\lfloor\frac{n}{p}\rfloor}{\lfloor\frac{k}{p}\rfloor}\left(\sum_{j=0}^{k\ \bmod\ p}\binom{n \bmod p}{j}\right)\right) \bmod p \\ =\left(2^{n\ \bmod\
p}f\left(\left\lfloor\frac{n}{p}\right\rfloor,\left\lfloor\frac{k}{p}\right\rfloor-1\right)+\binom{\lfloor\frac{n}{p}\rfloor}{\lfloor\frac{k}{p}\rfloor}\left(\sum_{j=0}^{k\ \bmod\ p}\binom{n \bmod p}{j}\right)\right) \bmod p f(n,k)=i=0∑k (in )modp=i=0∑k (⌊pi ⌋⌊pn ⌋ )(imodpnmodp )modp= i=0∑⌊pk ⌋−1
(i⌊pn ⌋ )(j=0∑p−1 (jnmodp ))+(⌊pk ⌋⌊pn ⌋ )(j=0∑k mod p (jnmodp )) modp= 2n mod pi=0∑⌊pk ⌋−1 (i⌊pn ⌋ )+(⌊pk ⌋⌊pn ⌋ )(j=0∑k mod p (jnmodp )) modp=(2n mod pf(⌊pn ⌋,⌊pk ⌋−1)+(⌊pk ⌋⌊pn ⌋ )(j=0∑k mod p (jnmodp )))modp
加号后面的可以预处理前缀和，递归计算即可。
时间复杂度：O(p2+Tlogp2n)O(p^2+T\log_p^2n)O(p2+Tlogp2 n)。
代码：
P3773 [CTSC2017] 吉夫特
> 给定长度为 nnn 的序列 aaa，求有多少个长度至少为 222 的不升子序列 a′a'a′ 满足：
>
> ∏i=2k(ai−1′ai′)≡1(mod2)\prod_{i=2}^k \binom{a'_{i-1}}{a'_{i}}\equiv1\pmod 2 i=2∏k (ai′ ai−1′ )≡1(mod2)
>
> 求出结果对 109+710^9+7109+7 取模。
首先根据 Lucas 定理有：
∏i=2k(ai−1′ai′) mod 2=∏i=2k(⌊ai−1′2⌋⌊ai′2⌋)(ai−1′ mod 2ai′ mod 2) mod 2>0\prod_{i=2}^k \binom{a'_{i-1}}{a'_{i}}\bmod 2 \\ =\prod_{i=2}^k\binom{\left\lfloor\frac{a'_{i-1}}{2}\right\rfloor}{\left\lfloor\frac{a'_{i}}{2}\right\rfloor}\binom{a'_{i-1}\bmod2}{a'_i\bmod2}\bmod2>0 i=2∏k (ai′ ai−1′
)mod2=i=2∏k (⌊2ai′ ⌋⌊2ai−1′ ⌋ )(ai′ mod2ai−1′ mod2 )mod2>0
说明 (ai−1′ mod 2ai′ mod 2)=1\binom{a'_{i-1}\ \bmod\ 2}{a'_i\ \bmod\ 2}=1(ai′ mod 2ai−1′ mod 2 )=1。
继续展开左边的这一坨分式，我们发现整体式子非 000 当且仅当 ai−1′a'_{i-1}ai−1′ 与 ai′a'_iai′ 在二进制每一位上 ai−1,j′≥ai,j′a'_{i-1,j}\geq a'_{i,j}ai−1,j′ ≥ai,j′ 成立。也就是定义 &\&& 表示按位与，ai−1′&ai′=ai′a'_{i-1}\&a'_{i}=a'_iai−1′ &ai′ =ai′ 。这也可以看作 ai′a'_iai′ 是 ai−1′a'_{i-1}ai−1′ 的子集。
注意到 aia_iai 互不相同，设 dpidp_idpi 表示结尾是 iii 的序列数量，枚举子集 jjj 刷表法转移即可。
时间复杂度：O(3log2maxai)O(3^{\log_2\max a_i})O(3log2 maxai )。
代码：
P2260 [清华集训 2012] 模积和
> 求：
>
> ∑i=1n∑j=1m(n mod i)(m mod j),i≠j\sum_{i=1}^n\sum_{j=1}^m(n\bmod i)(m\bmod j),i\neq j i=1∑n j=1∑m (nmodi)(mmodj),i=j
规定 n≤mn\leq mn≤m，容易想到把取模变成整除形式：
∑i=1n∑j=1m(n mod i)(m mod j),i≠j=∑i=1n∑j=1m(n−i⌊ni⌋)(m−j⌊mj⌋)−∑i=1n(n−i⌊ni⌋)(m−i⌊mi⌋)=∑i=1n∑j=1mnm−mi⌊ni⌋−nj⌊mj⌋+ij⌊ni⌋⌊mj⌋−∑i=1nnm−mi⌊ni⌋−ni⌊mi⌋+i2⌊ni⌋⌊mi⌋=n2m2−n2m−m2∑i=1ni⌊ni⌋−n2∑i=1mi⌊mi⌋+(∑i=1ni⌊ni⌋)(∑i=1mi⌊mi⌋)+m∑i=1ni⌊ni⌋+n∑i=1ni⌊mi⌋−∑i=1ni2⌊ni⌋⌊mi⌋\sum_{i=1}^n\sum_{j=1}^m(n\bmod i)(m\bmod
j),i\neq j \\ =\sum_{i=1}^n\sum_{j=1}^m\left(n-i\left\lfloor\frac{n}{i}\right\rfloor\right)\left(m-j\left\lfloor\frac{m}{j}\right\rfloor\right)-\sum_{i=1}^{n}\left(n-i\left\lfloor\frac{n}{i}\right\rfloor\right)\left(m-i\left\lfloor\frac{m}{i}\right\rfloor\right) \\ =\sum_{i=1}^n\sum_{j=1}^m
nm-mi\left\lfloor\frac{n}{i}\right\rfloor-nj\left\lfloor\frac{m}{j}\right\rfloor+ij\left\lfloor\frac{n}{i}\right\rfloor \left\lfloor\frac{m}{j}\right\rfloor-\sum_{i=1}^n nm-mi\left\lfloor\frac{n}{i}\right\rfloor-ni\left\lfloor\frac{m}{i}\right\rfloor+i^2\left\lfloor\frac{n}{i}\right\rfloor
\left\lfloor\frac{m}{i}\right\rfloor \\ =n^2m^2-n^2m-m^2\sum_{i=1}^n i\left\lfloor\frac{n}{i}\right\rfloor-n^2\sum_{i=1}^m i\left\lfloor\frac{m}{i}\right\rfloor+\left(\sum_{i=1}^n
i\left\lfloor\frac{n}{i}\right\rfloor\right)\left(\sum_{i=1}^mi\left\lfloor\frac{m}{i}\right\rfloor\right)+m\sum_{i=1}^ni\left\lfloor\frac{n}{i}\right\rfloor+n\sum_{i=1}^ni\left\lfloor\frac{m}{i}\right\rfloor-\sum_{i=1}^ni^2\left\lfloor\frac{n}{i}\right\rfloor \left\lfloor\frac{m}{i}\right\rfloor
i=1∑n j=1∑m (nmodi)(mmodj),i=j=i=1∑n j=1∑m (n−i⌊in ⌋)(m−j⌊jm ⌋)−i=1∑n (n−i⌊in ⌋)(m−i⌊im ⌋)=i=1∑n j=1∑m nm−mi⌊in ⌋−nj⌊jm ⌋+ij⌊in ⌋⌊jm ⌋−i=1∑n nm−mi⌊in ⌋−ni⌊im ⌋+i2⌊in ⌋⌊im ⌋=n2m2−n2m−m2i=1∑n i⌊in ⌋−n2i=1∑m i⌊im ⌋+(i=1∑n i⌊in ⌋)(i=1∑m i⌊im ⌋)+mi=1∑n i⌊in ⌋+ni=1∑n i⌊im ⌋−i=1∑n i2⌊in ⌋⌊im ⌋
我们知道：
∑i=1ni2=n(n+1)(2n+1)6\sum_{i=1}^n i^2=\frac{n(n+1)(2n+1)}{6} i=1∑n i2=6n(n+1)(2n+1)
因此整除分块即可。注意一些循环边界。
时间复杂度：O(n)O(\sqrt{n})O(n )。
代码：
P2522 [HAOI2011] PROBLEM B
> 给出 nnn 次询问，每次给定 a,b,c,d,ka,b,c,d,ka,b,c,d,k，求：
>
> ∑i=ab∑j=cd[gcd(i,j)=k]\sum_{i=a}^b\sum_{j=c}^d \left[\gcd(i,j)=k\right] i=a∑b j=c∑d [gcd(i,j)=k]
设：
f(a,b,c,d)=∑i=ab∑j=cd[gcd(i,j)=k]f(a,b,c,d)=\sum_{i=a}^b\sum_{j=c}^d \left[\gcd(i,j)=k\right] f(a,b,c,d)=i=a∑b j=c∑d [gcd(i,j)=k]
容斥则有：
ans=f(1,b,1,d)−f(1,a−1,1,d)−f(1,b,1,c−1)+f(1,a−1,1,c−1)ans=f(1,b,1,d)-f(1,a-1,1,d)-f(1,b,1,c-1)+f(1,a-1,1,c-1) ans=f(1,b,1,d)−f(1,a−1,1,d)−f(1,b,1,c−1)+f(1,a−1,1,c−1)
钦定 n≤mn \leq mn≤m，所以只需要求：
T(n,m)=∑i=1n∑j=1m[gcd(i,j)=k]T(n,m)=\sum_{i=1}^n\sum_{j=1}^m\left[\gcd(i,j)=k\right] \\ T(n,m)=i=1∑n j=1∑m [gcd(i,j)=k]
设 F(d)F(d)F(d) 表示最大公约数为 *** 的数对数量，G(d)G(d)G(d) 表示满足 d∣gcd(i,j)d\mid \gcd(i,j)d∣gcd(i,j) 的数对数量。得到：
G(d)=∑d∣kF(k)G(d)=⌊nd⌋⌊md⌋G(d)=\sum_{d\mid k}F(k) \\ G(d)=\left\lfloor\frac{n}{d}\right\rfloor\left\lfloor\frac{m}{d}\right\rfloor G(d)=d∣k∑ F(k)G(d)=⌊dn ⌋⌊dm ⌋
明显的莫比乌斯反演：
F(k)=∑k∣dμ(dk)G(d)=∑i=1⌊nk⌋μ(i)⌊nki⌋⌊mki⌋F(k)=\sum_{k\mid d}\mu\left(\frac{d}{k}\right)G(d) \\ =\sum_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}\mu(i)\left\lfloor\frac{n}{ki}\right\rfloor\left\lfloor\frac{m}{ki}\right\rfloor F(k)=k∣d∑ μ(kd )G(d)=i=1∑⌊kn ⌋ μ(i)⌊kin ⌋⌊kim ⌋
令 N=⌊nk⌋,M=⌊mk⌋N=\left\lfloor\frac{n}{k}\right\rfloor,M=\left\lfloor\frac{m}{k}\right\rfloorN=⌊kn ⌋,M=⌊km ⌋：
F(k)=∑i=1Nμ(i)⌊Ni⌋⌊Mi⌋F(k)=\sum_{i=1}^{N}\mu(i)\left\lfloor\frac{N}{i}\right\rfloor\left\lfloor\frac{M}{i}\right\rfloor F(k)=i=1∑N μ(i)⌊iN ⌋⌊iM ⌋
整除分块即可。
时间复杂度：O(N+nN)O(N+n\sqrt{N})O(N+nN )。
代码：
P2257 YY的GCD
> 求：
>
> ∑i=1n∑j=1misp(gcd(i,j))\sum_{i=1}^n\sum_{j=1}^m\operatorname{isp}(\gcd(i,j)) i=1∑n j=1∑m isp(gcd(i,j))
>
> 其中 isp(x)\operatorname{isp}(x)isp(x) 表示 xxx 是否为质数。
依旧令 n≤mn\leq mn≤m，推式子：
∑i=1n∑j=1misp(gcd(i,j))=∑p∈P∑i=1n∑j=1m[gcd(i,j)=p]\sum_{i=1}^n\sum_{j=1}^m\operatorname{isp}(\gcd(i,j))\\ =\sum_{p\in\mathbb{P}}\sum_{i=1}^n\sum_{j=1}^m\left[\gcd(i,j)=p\right] \\ i=1∑n j=1∑m isp(gcd(i,j))=p∈P∑ i=1∑n j=1∑m [gcd(i,j)=p]
显然和上一题一模一样。令 N=⌊np⌋,M=⌊mp⌋N=\left\lfloor\frac{n}{p}\right\rfloor,M=\left\lfloor\frac{m}{p}\right\rfloorN=⌊pn ⌋,M=⌊pm ⌋：
ans=∑p∈P∑i=1Nμ(i)⌊Ni⌋⌊Mi⌋=∑i=1n⌊ni⌋⌊mi⌋(∑p∣i,p∈Pμ(ip))ans=\sum_{p\in\mathbb{P}}\sum_{i=1}^{N}\mu(i)\left\lfloor\frac{N}{i}\right\rfloor\left\lfloor\frac{M}{i}\right\rfloor\\ =\sum_{i=1}^n\left\lfloor\frac{n}{i}\right\rfloor\left\lfloor\frac{m}{i}\right\rfloor\left(\sum_{p\mid
i,p\in\mathbb{P}}\mu\left(\frac{i}{p}\right)\right)\\ ans=p∈P∑ i=1∑N μ(i)⌊iN ⌋⌊iM ⌋=i=1∑n ⌊in ⌋⌊im ⌋ p∣i,p∈P∑ μ(pi )
右边的一坨令其为 f(i)f(i)f(i)，预处理即可。
时间复杂度：O(nloglogn+Tn)O(n\log\log n+T\sqrt{n})O(nloglogn+Tn )。
代码：
