这次 T3 T4 都很简单，可惜没有把握住。

数论是纯粹数学的分支之一，主要研究整数的性质。

定义

BSGS 算法用于求解关于\(x\)的方程\(a^x\equiv b\pmod p\)的解。

定义

素数筛用于求出\([2,n]\)范围内的质数。

定义

给出一个线性同余方程组：\(\begin{cases}x\equiv a_1\pmod{m_1}\\x\equiv a_2\pmod{m_2}\\ \ldots \\x\equiv a_n\pmod{m_n}\end{cases}\)，其中\(m_i\)两两互质，中国剩余定理用于求这样的方程组的解。

定义

乘法逆元通常用于在同余式中进行除法运算，其内容为：若\(ax\equiv 1\pmod p\)， 则称\(a\)在模\(p\)意义下的乘法逆元为\(x\)。

莫比乌斯函数

定义

根据唯一分解定理，\(n=\prod_{i=1}^{k} p_i^{a_i}\)。 \(\mu\)定义为 \[\mu(n)=\begin{cases}\mu(1)=1\\ \mu(n)=(-1)^k,\quad \forall a_i=1\\ \mu(n)=0,\quad \exists a_i>1\end{cases} \]

定义

给定\(a,b,c,n\)求对应函数的值：

\(f(a,b,c,n)=\sum_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor\)

\(g(a,b,c,n)=\sum_{i=0}^n i\lfloor\frac{ai+b}{c}\rfloor\)

\(h(a,b,c,n)=\sum_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor^2\)

定义

对于正整数\(n\)，欧拉函数是小于等于\(n\)的数中与\(n\)互质的数的数目，写作\(\varphi (n)\)。特别的，\(\varphi (1)=1\)。

定义

扩展欧几里得算法用于已知\(a,b\)，求解一组\(x,y\)，使得他们满足\(ax+by=\gcd(a,b)=d\)。