整除性

主要是针对素数的研究。

素数与合数

如果一个数 $x(x\in\mathbb{N})$ 的约数仅有 $1$ 和它本身，那么就称 $x$ 是质数（素数），特别地，$0$ 和 $1$ 不是质数，如果一个自然数不是质数，他就是合数。

可以用线性筛在 $O(n)$ 的时间内筛出所有质数，用 $O(\sqrt{r}+(r-l+1)\log(r-l+1))$ 的时间筛出区间内的所有质数。

$p$ 进赋值序列是刻画正整数的重要方式。可以将正整数表示到 $p$ 维空间上。

4. 类欧几里得问题

目的是求解 $y=\left\lfloor \dfrac{px+r} q\right\rfloor$ 这个函数相关的问题。

4.1 普通类欧

考虑：

$$f(a,b,c,n)=\sum_{i=0}^{n-1} \left\lfloor\dfrac{ai+b}{c}\right\rfloor$$

当 $a\ge c$ 或者 $b\ge c$ 时，让它们对 $c$ 取模，剩余部分就可以整除掉。于是转化为 $a,b<c$。

例题

刷提升 1