( ext{Some Definitions})
我们默认一个数的质因数分解为一下形式：
(P=prodlimits_{i=1}^{omega(P)}p_i^{e_i})
积性函数
若(forall pperp q,f(p)f(q)=f(pq))，则称(f(x))为积性函数。
若(forall p,qinmathbb{N_+},f(p)f(q)=f(pq))，则称(f(x))为完全积性函数。
加性函数
若(forall pperp q,f(p)+f(q)=f(pq))，则称(f(x))为加性函数。
若(forall p,qinmathbb{N_+},f(p)+f(q)=f(pq))，则称(f(x))为完全加性函数。
加性函数：
(omega(n)=sumlimits_{p|n}1)
完全加性函数：
(Omega(n)=sumlimits_{p^{alpha}|n}alpha)
积性函数：
(sigma_k(n)=sumlimits_{d|n}d^k=egin{cases}prodlimits_{i=1}^{omega(n)}(e_i+1)&k=0\prodlimits_{i=1}^{omega(n)}frac{p_i^{(e_i+1)k}-1}{p_i^k-1}&k
e0end{cases})
(sigma_0)一般简记为(d)或( au)，(sigma_1)一般简记为(sigma)。
(varphi(n)=sumlimits_{i=1}^n[iperp n]=nprodlimits_{i=1}^{omega}(1-frac1{p_i}))
(mu(n)=egin{cases}0&exists x^2|n\-1^{omega(n)}& ext{otherwise}end{cases})
完全积性函数：
(epsilon(n)=[n=1])
(id_k(n)=n^k)
(id_0)一般简记为(I)，(id_1)一般简记为(id)。
(lambda(n)=-1^{Omega(n)})
其它函数：
(alpha(p,n)=sumlimits_{i=1}^{+infty}lfloorfrac{n}{p^i}
floor)
定义是(p^{alpha(p,n)}|n!)。
(pi(n)=sumlimits_{i=2}^n[iinmathbb P](nge2))
Legendre符号
((frac ap)=egin{cases}0&a=0\1&exists xinmathbb F_{p},x^2equiv apmod p\-1&forall xinmathbb{F_p},x^2
otequiv apmod pend{cases})
完全积性。
阶
设(mge1wedge aperp m)，使(a^dequiv1pmod m)成立的最小(dinmathbb N_+)称为(a)对模(m)的阶，记做(delta_m(a))。
没有积性。
原根
当(delta_m(g)=varphi(m))时，称(g)是模(m)的原根。
性质：(forall iin[0,delta_m(a)),a^imod m)两两不同。
(m)有原根的充要条件是(min{1,2,4,p^k,2p^k}quad (p
e2,kge1))。
若一个数(p)存在原根，那么一定有(varphi(varphi(p)))个。
指标
(forall aperp m)，有唯一的表示(aequiv g^gammapmod mquad(gammain[0,varphi(m))))。我们称(gamma)为(a)以模(m)的以(g)为底的指标，记做(gamma_{m,g}(a))。
没有积性。
Dirichlet卷积
((f*g)(n)=sumlimits_{d|n}f(d)g(frac nd))
Bell级数
给定积性函数(f(x))与模数(p)，定义其Bell级数(f_p(x)=sumlimits_{n=0}^{+infty}f(p^n)x^n)。
(forall p,f_p(x)=g_p(x)Leftrightarrow f(x)=g(x))
((f+g)_p(x)=f_p(x)+g_p(x))
((f*g)_p(x)=f_p(x)g_p(x))
若(f(x))为完全积性函数，则(f_p(x)=frac1{1-f(p)x})。
( ext{Examples})
(epsilon_p(x)=1)
((id_k)_p(x)=frac1{1-p^kx})
((sigma_k)_p(x)=frac1{(1-x)(1-p^kx)})
(mu_p(x)=1-x)
(mu^2_p(x)=1+x)
(lambda_p(x)=frac1{1+x})
(varphi_p(x)=frac{1-x}{1-px})
(2^{omega(x)}_p=frac{1+x}{1-x})
Dirichlet级数
给定数论函数(f(n))，定义其Dirichlet级数为(mathfrak D_f(z)=sumlimits_{nge1}frac{f(n)}{n^z})
Riemann zeta函数：(zeta(z)=sumlimits_{nge1}frac1{n^z})
( ext{Properties})
(mathfrak D_fmathfrak D_g=mathfrak D_{f*g})
(mathfrak D_f+mathfrak D_g=mathfrak D_{f+g})
设(z=x+iy)，那么我们有：
(Re(mathfrak D_f(z))=sumlimits_{ngeq 1}frac{f(n)cos(ylog n)}{n^x})
(Im(mathfrak D_f(z))=sumlimits_{ngeq 1}frac{f(n)sin(ylog n)}{n^x})
若(f(n))为积性函数，那么(mathfrak D_f(z)=prodlimits_{pinmathbb P}(1+sumlimits_{ege1}frac{f(p^e)}{p^{ez}}))。
(mathfrak D_f'(z)=-sumlimits_{nge1}frac{f(n)ln(n)}{n^z})
( ext{Examples})
(mathfrak D_{epsilon}(z)=1)
(mathfrak D_{id_k}(z)=zeta(z-k))
(mathfrak D_{mu}(z)=frac1{zeta(z)})
(mathfrak D_{varphi}(z)=frac{zeta(z-1)}{zeta(z)})
(mathfrak D_{sigma_k}(z)=zeta(z-k)zeta(z))
( ext{Some Theorems})
Euler定理
(forall aperp m,a^{varphi(m)}equiv1pmod m)
Ex Eluer定理
(forall bgevarphi(m),a^bequiv a^{bmodvarphi(m)+varphi(m)}pmod m)
CRT
设(m_1,cdots,m_kinmathbb{N_+})两两互质，对于同余方程组(forall a_1,cdots a_kin N,xequiv a_i(mod) (m_i)(iin[1,k]))。
令(m=prodlimits_{i=1}^{k}m_i,m=m_iM_i,M_i^{-1})是(mod m_i)意义下(M_i)的逆元，则同余方程组的解为(xequiv sumlimits_{i=1}^{k}M_iM_i^{-1}a_ipmod m)。
Lucas定理
({nchoose m}equiv{lfloorfrac np floorchooselfloorfrac mp floor}{nmod pchoose mmod p}pmod p)
Wilson定理
((p-1)!equiv-1pmod pLeftrightarrow pinmathbb P)
Euler准则
((frac ap)equiv a^{frac{p-1}2}pmod p)
Mobiüs反演定理
(f=g*ILeftrightarrow g=f*mu)
(F(n)=sumlimits_{n|d}f(d)Leftrightarrow f(n)=sumlimits_{n|d}mu(frac dn)F(n))
Lagrange定理
若一多项式(f(x))的系数在(mathbb{F_{p}})内，则(f(x)equiv0pmod p)最多有(deg f)个根。
Gauss二次互反律
若(p,q)为不同的奇素数，则((frac pq)(frac qp)=(-1)^{frac{(p-1)(q-1)}4})。
Fermat多边形数定理
每一个正整数最多可以表示为(n)个(n)边形数之和。
第(i)个(n)边形数为(frac{i[(n-2)i-(n-4)]}{2})。
Fermat大定理
(forall n>2,x^n+y^n=z^n)无正整数解。
Goldbach猜想
大于(2)的偶数都可表示成两个素数之和。
弱Goldbach猜想：大于(5)的奇数都可以表示成三个素数之和。
Waring问题
(forall kinmathbb{N_+},exists g(k)inmathbb{N_+},s.t.forall ainmathbb{N_+})，(a)可以被表示为至多(g(k))个(i^k(iinmathbb{N_+}))形式的数的和。
这个猜想是正确的，还有一个猜想是(g(k)=2^k+lfloor(frac32)^k
floor-2)。
Pisano period
( ext{Some Identities About Some Functions})
(mu*I=epsilon)
(I*id_i=sigma_i)
(varphi*I=id)
(mu*id=varphi)
(I*frac{mu}{id}=frac{varphi}{id})
(d^2*mu=mu^2*d)
(2^{omega(n)}=mu^2*I)
(d(ij)=sumlimits_{x|i}sumlimits_{y|j}[xperp y])
(varphi(ab)=frac{varphi(a)varphi(b)(a,b)}{varphi(gcd(a,b))})
(prodlimits_{i=1}^p(x+i)=x(x^{p-1}-1)qquad [x^i]inmathbb{F_p})
(f(1)=1Rightarrow f^p=epsilonqquad f(i)inmathbb{F_p})
若(h)是完全积性函数，则(h(f*g)=(hf)*h*g)。
对任意数论函数(h)，(h(f*g)=(hf)*g+(hg)*f)。
( ext{Some Algorithms})
Ex Euclid
求解(ax+by=gcd(a,b)=d)。
当(b=0)时，(gcd(a,b)=a)，显然存在一对整数解(x=1,y=0)。
若(b
e0)，设(ax_1+by_1=gcd(a,b)=gcd(b,amod b)=bx_2+(amod b)y_2)。
我们有(amod b=a-lfloorfrac{a}{b}
floor b)。
代入得(ax_1+by_1=ay_2+b(x_2-lfloorfrac{a}{b}
floor y2))。
也就是说(x_1=y_2 , y_1=x_2-lfloorfrac{a}{b}
floor y_2)。
如此递归直到(b=0)，然后逆推回来。
注意求的解是绝对值最小的一组。
Ex CRT
相对CRT而言(m_i)不一定两两互质。
考虑数归求解。
第一个方程很容易解。
现在我们假设前(k-1)个方程的特解是(x)，(M_k=operatorname{lcm} m_i(iin[1,k))，则(x+iM_{k-1}(iin Z))是前(k-1)个方程的通解。
现在我们还要满足第(k)个方程，即求出一个(t)使得(x+tM_{k-1}equiv a_k(mod m_k))，然后前(k)个方程的特解就是(x+tM_{k-1})。
上面这个方程还是(axequiv bpmod m)形式的，它等同于(ax+my=b)。
如果这个方程有解的充要条件是(gcd(a,m)|b)。
用exgcd求出(ax+my=gcd(a,m))的一组解(x_0,y_0)。
那么有(a(frac{x_0b}{gcd(a,m)})+m(frac{y_0b}{gcd(a,m)})=b)。
BSGS
求（最小的）满足(a^xequiv bpmod m)的(x)。其中(aperp m)。
令(x=fg-h)，则有((a^f)^gequiv ba^hpmod m)。
预处理(hin[0,g))的(ba^hmod m)，然后枚举(fin[0,frac pg])查表。
显然(g=sqrt p)时最优。
Ex BSGS
(a otperp m)
令(d=gcd(a,m))，有解的充要条件是(d|bvee b=1)。
否则我们有(a^{x-1}frac adequivfrac bdpmod{frac md})。
一直递归直到满足停止条件：若(d=1)直接BSGS。若(m)很小直接暴力。
此时有(a^{x-k}frac{a^k}{prod d}equivfrac b{prod d}pmod{frac m{prod d}})。
记得把求出来的答案加上(k)。
Ex Lucas
求({nchoose m}mod q)
( ext{Part.1})
质因数分解(q=prodlimits_{i=1}^{omega(q)}p_i^{e_i})。
(forall iin[1,omega(q)])求出({nchoose m}mod{p_i^{e_i}})，然后CRT合并。
( ext{Part.2})
({nchoose m}equivfrac{n!}{m!(n-m)!}pmod{p_i^{e_i}})
然后我们发现并不一定有逆元。
所以求出(A=alpha(p_i,n),B=alpha(p_i,m),C=alpha(p_i,n-m))，那么(frac{n!}{m!(n-m)!}equiv frac{frac{n!}{p_i^A}}{frac{m!(n-m)!}{p_i^{B+C}}}p_i^{A-B-C}pmod{p_i})，这样就能保证求出逆元了。
( ext{Part.3})
根据定义，(A=alpha(p_i,n)=sumlimits_{j=1}^{+infty}lfloorfrac n{p_i^j}
floor)。
但是(frac{n!}{p_i^A}mod{p_i^{e_i}})似乎不太好算。
把(n!)中是(p_i)的倍数的项提出来，(n!equiv p_i^{lfloorfrac n{p_i}
floor}lfloorfrac n{p_i}
floor!prodlimits_{j=1}^n[jperp p_i]jpmod{p_i^{e_i}})。
(lfloorfrac n{p_i}
floor!)可以递归处理。
所以我们可以只要考虑(prodlimits_{j=1}^n[jperp p_i]jmod{p_i^{e_i}})。
这东西显然以(p_i^{e_i})为循环节，即(prodlimits_{j=1}^n[jperp p_i]jequiv(prodlimits_{j=1}^{p_i^{e_i}}[jperp p_i]j)^{frac n{p_i^{e_i}}}(prodlimits_{j=1}^{nmod p_i^{e_i}}[jperp p_i]j)pmod{p_i^{e_i}})。
两边都可以(O(p_i^{e_i}))暴力算。
总的复杂度大概是(O(qlog q))。
Cipolla
给定(a,p)，求(x^2equiv apmod p)的解。
(p=2vee a=0)特判。
然后利用Euler准则计算(a)是否为二次剩余，判断是否有解。
找一个(w)使得((frac{w^2-a}p)=-1)，期望随机次数为(2)。
然后计算((w+sqrt{w^2-a})^{frac{p+1}2})，就可以得到一个(x)，另一个就是(p-x)。
根据Lagrange定理，算出来的一定是个整数。
求原根
求模(m)的原根(g)。
有原根的充要条件在定义部分已经写了。
分解(varphi(m)=prodlimits_{i=1}^{omega(varphi(m))}p_i^{e_i})。
枚举(ain[2,varphi(m)))，对每个(p_i)检测是否有(a^{frac{varphi(m)}{p_i}}
otequiv1pmod m)。
如果(forall iin[1,omega(varphi(m))])都成立，那么这个(a)就是一个原根。
复杂度是(O(varphi(m)log^2m))的，不过如果只要求最小原根的话大概就是(O(sqrt[4]mlog^2m))的。
(k)次剩余
给定(a,k,m)，求(x^kequiv apmod m)的解。
( ext{Part.1})
(aperp mwedge m=p^tqquad(p e2))
找到(m)的一个原根(g)。
利用BSGS求出(gamma_{m,g}(a))，设(y=gamma_{m,g}(x))，然后两边对(g)取对数，那么我们要解的就是(ykequivgamma_{m,g}(a)pmod{varphi(m)})。
exgcd解一下就好了。
( ext{Part.2})
(a otperp mwedge m=p^tqquad(p e2))
(a=0)
显然(x={p^i|iin[lceilfrac tk ceil,t)})。
(p|a)
不妨设(a=sp^r)，显然必须满足(k|r)才能有解。
令(x=yp^{frac rk})，那么我们要解的就变成了(y^kequiv rpmod{p^{t-r}})。
此时一定会有(rperp p^{t-r})，套用( ext{Part.1})就好了。
( ext{Part.3})
(m=prodlimits_{i=1}^{omega(m)}p_i^{e_i}qquad(p_i e2))
分别对每个(p_i^{e_i})调用( ext{Part.2})。
这样我们就求出了(forall iin[1,omega(m)],xequiv x_ipmod{p_i^{e_i}})。
注意每个(x_i)可能有多解，枚举每一个CRT合并即可。
根据Lagrange定理总解数不超过(k)。
( ext{Part.4})
(m=2^sn,n=prodlimits_{i=1}^{r}p_i^{t_i}qquad(p_i e2))
考虑先计算出(y^kequiv apmod n)。
那么对应的(y^kequiv apmod{2n})的解就是(y,y+n)的其中一个或者没有。
枚举每个(y)然后一路做上去就行了。
Miller-Rabin
判断一个数是否是素数。
根据Euler定理，若一个数(n)不满足(forall ain[2,n),a^{n-1}equiv1pmod n)，那么(n)一定不是质数。
但是它的逆否命题并不成立。
但是我们知道，(x^2equiv1pmod pwedge x<pRightarrow x=1vee x=p-1)。
所以当(a^{n-1}equiv1pmod nwedge 2|n-1)成立时，我们再计算(a^{frac{n-1}2}equivpm1pmod n)是否成立。
如果不成立，那么说明(n)一定不是素数。
如果(a^{frac{n-1}2}equiv-1pmod n)，那么说明(n)可能是素数，算法结束。
如果(a^{frac{n-1}2}equiv1pmod n)，那么说明(n)可能是素数，继续检测。
我们把这个过程叫做以(a)为底的二次探测，把能够通过这个检测是合数叫做以(a)为底的强伪素数。
实际上当我们取了(k)个(a)时，这个算法的正确率大概是(4^{-k})。
所以我们可以直接rand一些([2,n))的数进行检测。
时间复杂度为(O(klog^2n))。
Pollard-Rho
质因数分解(n)。
本质依旧是试除法。
我rand一个(x)，看(n)是否是(x)的约数。
然后更优秀的试除法是我rand一个(x)，看是否有(nperp x)。
根据生日悖论，我们rand出(x_1,cdots,x_m)，若(exists i,j,s.t.left|x_i-x_j
ight|
otperp n)，那么我们就找到了(n)的一个约数((left|x_i-x_j
ight|,n))。根据上古论文的证明(m=O(sqrt[4]n))。
但是直接检测是(O(m^2))的，这等于说复杂度还是(O(sqrt n))。
假如我们只取(left|x_i-x_j
ight|)，这样就能(O(m))地检测了。
但是这样找到的概率就会低很多，所以我们需要一个优秀的rand方法。
rand一个(c)，令(f(x)=x^2+cpmod n)，再rand一个(x_0)，并且有(x_i=f(x_{i-1}))。这个序列很优秀。
根据Mandelbrot集的相关知识，这个序列确实很优秀。
但是做了很多次迭代之后很可能会有(x_t=x_squad(t>s))，这样就出现了一个环。
有一个科技叫做floyd判圈法，大概就是你在迭代求(f(x_i))同时求(f(x_{2i}))。
假如从(r)开始有一个长度为(c)的环，那么恒有(f_i=f_{i+c}quad(ige r))。我们能够保证在(r+c)次迭代以内判出环。
然后我们发现(gcd)太慢了，即使加了二进制优化/记忆化等优化之后它还是很慢，并且是复杂度大头。
根据(gcd)的性质，我们可以累(u)个(left|x_i-x_{i+1}
ight|)，然后直接计算((prodlimits_{i=1}^uleft|x_i-x_{i+1}
ight|mod n,n))。
考虑用倍增做这个过程，先rand长度为(2)的序列，再rand长度为(4)的序列...
并且当我们累了(127)项时，直接计算一次(gcd)。
这样相对而言可以把复杂度平衡得较为不错。
总的复杂度大概是(O(sqrt[4]n))级别的。
卷积
我们知道Dirichlet卷积就是将两个数论函数的Dirichlet级数相乘，直接乘的时间复杂度为(O(nlog n))。
对于积性函数而言，其Dirichlet级数可以写成(prodlimits_{pinmathbb P}(1+sumlimits_{ege1}frac{f(p^e)}{p^{ez}}))。
那么我们就可以将求积性函数与积性函数的Dirichlet卷积做到(O(n))，将求积性函数与任意数论函数的Dirichlet卷积做到(O(nloglog n))。
杜教筛
求(F=sum f)的(F(n))。
构造(f*g=h)，其中(g,h)满足能够快速求出(g,H=sum h)。
那么可以得到(H(n)=sumlimits_{d=1}^ng(d)F(lfloorfrac nd
floor))。
然后我们把右边的(d=1)的项提出来并且移项，(F(n)=H(n)-sumlimits_{d=2}^n g(d)F(lfloorfrac nd
floor))。
我们先线性筛(T)范围内的(f,F)，然后后面的用数论分块+记忆化解决（可以发现要有用的下标都是(lfloorfrac ni
floor)，因此可以用(lfloorfrac ni
floor)的(i)存下标）。
如果我们默认能够(O(n))筛出前(n)项的(f)并且能够快速计算(H)在所有(lfloorfrac ni
floor)的值，那么复杂度为(O(T+frac n{sqrt T}))，当(T=n^{frac23})时取到最优复杂度(O(n^{frac23}))。
Cy筛.1
求(H=sum h)的(H(n))。
构造(f*g=h)，其中(f,g)满足能够快速求出(F=sum f,G=sum g)。
先回到定义式上：(H(n)=sumlimits_{i=1}^nsumlimits_{d|n}g(d)f(frac{i}{d})=sumlimits_{d=1}^ng(d) sumlimits_{i=1}^{lfloorfrac{n}{d}
floor}f(i))。
画出(xy=n)的曲线的图像，每个整点((x,y))有一个权值(f(x)g(y))，(H(n))就等价于曲线下整点的权值和。
利用经典容斥套路可以得到：(H(n)=sumlimits_{i=1}^{lfloorsqrt n
floor}f(i)G(lfloorfrac ni
floor)+sumlimits_{i=1}^{lfloorsqrt n
floor}g(i)F(lfloorfrac ni
floor)-F(lfloorsqrt n
floor)G(lfloorsqrt n
floor))。
时间复杂度为(O(sqrt n))。
Cy筛.2
求(f=g^m,F=sum f)的(F(n))。其中(g)满足能够快速求出(G=sum g)。
考虑数论分块+倍增，维护(P=[1,T]cup{lfloorfrac ni
floor|iin[1,lfloorfrac nT
floor]})下标位置的取值。
那么我们要解决的就是已知(F=sum f,G=sum g)在(P)中下标上的取值，求(H=sum h=sum f*g)在(P)中下标上的取值。
对于([1,T])部分，我们可以直接暴力差分还原(f,g)，卷积得到(h)，再前缀和得到(H)，时间复杂度为(O(Tlog T))。
对于({lfloorfrac ni
floor|iin[1,lfloorfrac nT
floor]})部分，考虑用Cy筛.1中的方法计算。
先回到定义式上：(H(n)=sumlimits_{i=1}^nsumlimits_{d|n}g(d)f(frac{i}{d})=sumlimits_{d=1}^ng(d) sumlimits_{i=1}^{lfloorfrac{n}{d}
floor}f(i))。
画出(xy=n)的曲线的图像，每个整点((x,y))有一个权值(f(x)g(y))，(H(n))就等价于曲线下整点的权值和。
利用经典容斥套路可以得到：(H(n)=sumlimits_{i=1}^{lfloorsqrt n
floor}f(i)G(lfloorfrac ni
floor)+sumlimits_{i=1}^{lfloorsqrt n
floor}g(i)F(lfloorfrac ni
floor)-F(lfloorsqrt n
floor)G(lfloorsqrt n
floor))。
不难发现所有需要用到的(f,g,F,G)的下标都在(P)中。
这一部分的时间复杂度为(sumlimits_{i=1}^{frac nT}O(sqrt{frac ni})=frac n{sqrt T})。
因此总的时间复杂度为(O((Tlog T+frac n{sqrt T})log m))，取(T=n^{0.6})时比较优秀。
Min_25筛
求(sumlimits_{x=1}^nf(x))，其中(f(x))是一个积性函数，且(f(p))是一个简单多项式，(f(p^e))可以快速计算。
记(min(x))表示(x)的最小质因子。用(p)表示质数，(p_i)表示第(i)个质数，(S_n={lfloorfrac nm floor|minmathbb{N_+}})。
考虑枚举(x)的最小质因子，再枚举它的出现次数：
注意到若(x)是合数，则(x)的最小质因子不会超过(lfloorsqrt x floor)，因此我们有：
设(g_{n,m}=sumlimits_{x=2}^n[min(x)>p_m]f(x),h_n=sumlimits_{p=2}^nf(p))，那么我们可以得到递推式：
而我们要求的(sumlimits_{x=1}^nf(x)=g_{n,0}+1)。
注意到若(mgesqrt n)，则(g_{n,m}=h_n-h_m)。且我们只需要求出(xin S_n)的(g_{x,m})。
因此如果我们求出了需要的(h)，那么我们就可以爆搜求出(g)。
接下来考虑如何求出(h)。容易发现我们只需要求出(xin S_n)的(h_x)。
只考虑(f(p))为完全积性函数的情况，其它情况可以拆成若干个完全积性函数的和。
设(h'_{n,m}=sumlimits_{x=2}^n[xinmathbb P ext{ or }min(x)>p_m]f(x))，那么我们可以得到递推式：
而我们要求的(h_x=h'_{x,|mathbb P|})。
将第二维滚掉然后暴力dp即可。
整体的时间复杂度分为计算(g)和计算(h)两部分。
计算(h)部分的如下：
注意到每个(lfloorfrac nm
floor=i)只会对不超过(sqrt i)的素数产生转移，因此时间复杂度如下：
计算(g)部分的时间复杂度为(O(n^{1-epsilon}))，但是在(nle 10^{13})的前提下不会超过(O(frac{n^{frac34}}{log n}))。