数论

Published: October 28, 2019 by Daltao

• Categories:
• algorithm 101

• Tags:

• 原根
• 上下取整运算
  • 上下整除互换
  • 下整除结结合性
  • 上整除结合性
  • 上下整除混用
• 向下取整数论分块
• 数论分块记忆化搜索的时间复杂度
• 最小立方倍数问题
• 积性函数
• 完全积性函数
• 莫比乌斯函数
• 乘法逆元
• 一些环上定长位移问题
• 倍数和约数加总及还原技巧
  • 容斥原理统计倍数出现次数及还原
  • 容斥原理统计约数出现次数及还原
  • 统计带修改的倍数出现次数及还原
  • 统计带修改的约数出现次数及还原
• 最多k个不同数字组成的n的倍数
• n的因子中最长反链
• 1到n取k个数的可能的和
• 离散对数
• 最小分母分子
• 公约数公倍数问题
• 取模运算的一些问题
• 类欧几里德算法
• 一些快速计算的技巧
• 参考资料

原根

若正整数a与m互质，由欧拉定理知道存在某个正整数d，满足$a^d=1\pmod m$，比如令d为 欧拉函数$\varphi(m)$。在所有满足上述条件的d中最小的可能取值记作$\delta_m(a)$，由于$\delta_m(a)\leq \varphi(m)$，若等号成立，则成a是模m的原根。

存在模m的原根，当且仅当m为下列形式：$2$，$4$，$p^a$，$2p^a$。这里p是奇素数，a为正整数。

要找模m最小的原根，我们知道对于任意数a，都有$\delta_m(a)|\varphi(m)$。因此我们可以先找到$\varphi(m)$的所有素数因子$p_1,p_2,\ldots,p_k$。根据资料，模p的最小原根应该是$m^{\frac{1}{4}}$级别的，因此可以直接暴力从小到大枚举所有可能的原根。当我们枚举到a时，如果a不是原根，那么至少存在一个数$1\leq i \leq k$，使得$\delta_m(a)|\frac{\varphi(m)}{p_i}$。此时必定有$a^{\frac{\varphi(m)}{p_i}}=1$。因此我们可以通过这个条件来辨别一个数是否是原根。

上下取整运算

上下整除互换

对于任意整数$a$和正整数$b$，下面命题均成立。

$$\left\lceil \frac{a}{b} \right\rceil = \left\lfloor \frac{a+b-1}{b} \right\rfloor \\ \left\lfloor \frac{a}{b} \right\rfloor = \left\lceil \frac{a-b+1}{b} \right\rceil$$

下整除结结合性

对于任意整数a和正整数b,c，下面等式成立：

$$\left\lfloor \frac{\left\lfloor \frac{a}{b} \right\rfloor}{c} \right\rfloor =\left\lfloor \frac{a}{bc} \right\rfloor$$

证明：

记$p_1=\left\lfloor \frac{\left\lfloor \frac{a}{b} \right\rfloor}{c} \right\rfloor$，那么由整除的定义我们可以得到

$$\left\lfloor \frac{a}{b} \right\rfloor= p_1c+r_1$$

其中$r_1 < c$。进一步利用整除的定义得到：

$$a=(p_1c+r_1)b+r_2=p_1cb+r_1b+r_2$$

其中$r_2 < b$。对公式两边同时除去$bc$得到：

$$\frac{a}{bc}=p_1+\frac{r_1b+r_2}{bc}$$

由于：

$$r_1b+r_2<r_1b+b=b(r_1+1)\leq bc$$

因此我们认为$\left\lfloor \frac{r_1b+r_2}{bc} \right\rfloor = 0$。对左右两端都向下取整得到：

$$\left\lfloor \frac{a}{bc} \right\rfloor=p_1+\left\lfloor \frac{r_1b+r_2}{bc} \right\rfloor = p_1=\left\lfloor \frac{\left\lfloor \frac{a}{b} \right\rfloor}{c} \right\rfloor$$

命题得证。

上整除结合性

对于任意整数a和正整数b,c，下面等式成立：

证明：

$$\left\lceil \frac{\left\lceil \frac{a}{b} \right\rceil}{c} \right\rceil =\left\lceil \frac{a}{bc} \right\rceil$$

记$p_1=\left\lceil \frac{\left\lceil \frac{a}{b} \right\rceil}{c} \right\rceil$，那么由整除的定义我们可以得到

$$\left\lceil \frac{a}{b} \right\rceil= p_1c-r_1$$

其中$r_1 < c$。进一步利用整除的定义得到：

$$a=(p_1c-r_1)b-r_2=p_1cb-r_1b-r_2$$

其中$r_2 < b$。对公式两边同时除去$bc$得到：

$$\frac{a}{bc}=p_1-\frac{r_1b+r_2}{bc}$$

由于：

$$r_1b+r_2<r_1b+b=b(r_1+1)\leq bc$$

因此我们认为$\left\lceil -\frac{r_1b+r_2}{bc} \right\rceil = 0$。对左右两端都向上取整得到：

$$\left\lceil \frac{a}{bc} \right\rceil=p_1+\left\lceil-\frac{r_1b+r_2}{bc} \right\rceil = p_1=\left\lceil \frac{\left\lceil \frac{a}{b} \right\rceil}{c} \right\rceil$$

命题得证。

上下整除混用

命题：对于任意非负整数a和正整数b，c，都有$\left\lceil \frac{\left\lfloor \frac{a}{b} \right\rfloor}{c}\right\rceil,\left\lfloor \frac{\left\lceil \frac{a}{b} \right\rceil}{c} \right\rfloor \in \{\left\lfloor \frac{a}{bc} \right\rfloor,\left\lceil \frac{a}{bc} \right\rceil \}$

证明：

考虑到$\left\lfloor \frac{a}{bc} \right\rfloor \leq \left\lceil \frac{\left\lfloor \frac{a}{b} \right\rfloor}{c}\right\rceil, \left\lfloor \frac{\left\lceil \frac{a}{b} \right\rceil}{c} \right\rfloor \leq \left\lceil \frac{a}{bc} \right\rceil$，而$\left\lfloor \frac{a}{bc} \right\rfloor + 1\geq \left\lceil \frac{a}{bc} \right\rceil$，因此命题可以直接得证。

题目1：你需要操作一个数$x$，初始为0，经过若干次操作后，你要让它变成$n$。你可以执行四类操作：

1. 将$x$变成$2x$，花费$A$
2. 将$x$变成$3x$，花费$B$
3. 将$x$变成$5x$，花费$C$
4. 将$x$变成$x+1$或$x-1$，花费$D$

问达成目标最小的花费是多少，这里$0\leq n\leq 10^{18},0\leq A,B,C,D\leq 10^{9}$

一个直接的想法是DP，但是无路可走，因为数值范围太大了。但是实际上这个问题的解法非常简单。

首先费用最多为$60A+D$，因此结果一定可以用长整型来表示。

我们逆向计算结果，即我们手头的数为$n$，希望将其变成$0$。假设我们下一次操作为除上$d$，但是$x$不能被$d$整除，那么我们可以通过增大或减少$d$，让其能被整除。可以证明，我们最多将其增大到$\left\lceil \frac{x}{d} \right\rceil d$或减少到$\left\lfloor \frac{x}{d} \right\rfloor d$，因为我们每多增大$d$，不如在除$d$后增加$1$的费用低。因此我们给出了一个暴力递归算法。

记$f(m)$表示从$m$降低到$0$的最小费用。那么我们这里证明$f$的可能不同参数的数目。可以发现其参数只可能为

$$\left\lfloor \frac{m}{2^{\alpha}3^{\beta}5^{\gamma}} \right\rfloor, \left\lceil \frac{m}{2^{\alpha}3^{\beta}5^{\gamma}} \right\rceil$$

两种形式。可以发现$\alpha \leq 60, \beta \leq 40, \gamma \leq 12$，因此总状态的上限为$28800$。这里假如我们用哈希表来做缓存，时间复杂度可以优化到$O((\log_2n)^3)$。

一道题目。

向下取整数论分块

面对下面这样的函数：

$$\sum_{i=1}^{m}f(\left\lfloor{\frac{n}{i}}\right\rfloor)$$

其中$m\leq n$。

其中计算$f(x)$的时间复杂度为$O(1)$，求问你可以多快获得结果。

很显然暴力计算的时间复杂度将是$O(n)$。虽然称不上优秀，但是至少简单。但是假如$n$很大，那么计算起来就是一件轻松的事情了。

for(int i = 1; i <= m; i++)
{
    sum += f(n / i);
}

通过观察可以发现存在很多$i<j$但$\left\lfloor{\frac{n}{i}}\right\rfloor=\left\lfloor{\frac{n}{j}}\right\rfloor$的情况，比如当$n=4,i=3,j=4$。

我们称$\left\lfloor{\frac{n}{i}}\right\rfloor$为$i$的下整值。记下整值为$x$的所有的$i$的集合$\{i_1,i_2,\ldots,i_k\}$为$x$的导出集合，记作$E(x)$。

并且很容易发现拥有相同下整值的数值往往是连续的。实际上，若$i<j$且$\left\lfloor{\frac{n}{i}}\right\rfloor=\left\lfloor{\frac{n}{j}}\right\rfloor$成立时，对于任意$i\leq x \leq j$，都有$\left\lfloor{\frac{n}{i}}\right\rfloor \leq \left\lfloor{\frac{n}{x}}\right\rfloor \leq \left\lfloor{\frac{n}{j}}\right\rfloor$，即$\left\lfloor{\frac{n}{i}}\right\rfloor = \left\lfloor{\frac{n}{x}}\right\rfloor = \left\lfloor{\frac{n}{j}}\right\rfloor$。

我们可以将拥有相同下整值的值合并在一起计算。对于任意$i$，记$j=\left\lfloor\frac{n}{\left\lfloor\frac{n}{i}\right\rfloor}\right\rfloor$，可以推出：$\left\lfloor\frac{n}{i}\right\rfloor\leq\frac{n}{j}$以及$\frac{n}{j+1}<\left\lfloor\frac{n}{i}\right\rfloor$。由后者可知$max(E(\left\lfloor\frac{n}{i}\right\rfloor))\leq j$，而由前者可知$\left\lfloor\frac{n}{j}\right\rfloor \leq \left\lfloor\frac{n}{i}\right\rfloor\leq \left\lfloor\frac{n}{j}\right\rfloor$，结合得到$j=max(E(\left\lfloor\frac{n}{i}\right\rfloor))$。

$$\left\{ \begin{array}{lll} \min(E(x))&=&\left\lfloor\frac{n}{x+1}\right\rfloor+1\\ \max(E(x))&=&\left\lfloor\frac{n}{x}\right\rfloor \end{array} \right.$$

我们要做的就是枚举可能的下整值，并合并计算。

int sum = 0;
for(int i = 1, r; i <= m; i = r + 1)
{
    int x = n / i;
    r = min(m, n / x);
    sum += f(x) * (r - i + 1)
}

上面我们就优化了原先的代码，加入了合并计算的能力。

代码优化是优化了，但是我们现在的时间复杂度究竟是多少呢？很显然时间复杂度为$O(B)$，其中$B$是总共的分块数目，同样也是可能的下整值数量。考虑到对于$1,2,\ldots,\sqrt{n}$，它们的下整值落在$\{\left\lfloor\frac{n}{1}\right\rfloor,\left\lfloor\frac{n}{2}\right\rfloor,\ldots,\left\lfloor\frac{n}{\sqrt{n}}\right\rfloor\}$，而对于任意，而对于任意$i>\sqrt{n}$，其下整值一定落在$\{1,2,\ldots,\sqrt{n}\}$中。因此可能的下整值最多有中。因此可能的下整值最多有$2\sqrt{n}$种。借此我们得到了时间复杂度的上限。借此我们得到了时间复杂度的上限$O(\sqrt{n})$。

题目1：要求计算$\sum_{i=1}^n f(\left\lfloor \frac{n+i}{2i} \right\rfloor)$。其中$n\leq 10^{12}$，且$f(x)$可以$O(1)$求解。

这个和通常的数论分块公式有略微不同。我们可以用下整除的结合性进行化简：

$$\begin{aligned} \left\lfloor \frac{n+i}{2i} \right\rfloor &= \left\lfloor\frac{\left\lfloor \frac{n+i}{i} \right\rfloor}{2}\right\rfloor\\ &=\left\lfloor\frac{\left\lfloor \frac{n}{i} \right\rfloor+1}{2}\right\rfloor \end{aligned}$$

我们记$g(x)=\left\lfloor\frac{x+1}{2}\right\rfloor$，那么我们可以得到$f(\left\lfloor \frac{n+i}{2i} \right\rfloor)=fg(\left\lfloor \frac{n}{i} \right\rfloor)$，其中$fg$也是$O(1)$计算的函数。现在的问题就是一个普通的数论分块问题了，时间复杂度为$O(\sqrt{n})$。

题目2：给定$n$个有效区间，第$i$个有效区间为$[l_i,r_i]$，要求计算有多少可能的周期$T$，满足$1\leq T\leq m$，且对于任意数$x=T,2T,3T,\ldots$，如果$x\leq m$，则至少一个有效区间包含$x$。其中$1\leq n\leq 100$，$1\leq m\leq 10^9$

首先我们可以认为所有有效区间都不相邻或相交（否则我们可以合并这些区间）。之后我们考虑所有的非有效区间$[L_i,R_i]$，可以发现这样的区间最多只有$n+1$个。由于不能有$x$落在这样的区间中，因此，我们需要保证$\left\lfloor \frac{L_i-1}{T} \right\rfloor=\left\lfloor \frac{R_i}{T} \right\rfloor$。

于是现在我们等价于要计算有多少$T$，满足上面列出的$O(n)$个约束条件。可以发现每个约束条件（数论分块技巧）最多只会给出$O(\sqrt{m})$个可能区间，因此我们只需要合并这些区间即可。简单的方式就是用优先队列完成，时间复杂度为$O(n\sqrt{m}\log_2n)$。如果预处理所有的左右边界，并用基数排序进行排序，可以将时间复杂度降低到$O(n\sqrt{m})$。

题目3：要求计算$\sum_{i=1}^nf(\left\lceil\frac{n}{i}\right\rceil)$，其中$f(x)$可以$O(1)$计算。且$1\leq n\leq 10^{12}$。

可以做如下转换：

$$\begin{aligned} \sum_{i=1}^nf(\left\lceil\frac{n}{i}\right\rceil)&=\sum_{i=1}^nf(\left\lfloor\frac{n+i-1}{i}\right\rfloor)\\ &=\sum_{i=1}^nf(1+\left\lfloor\frac{n-1}{i}\right\rfloor) \end{aligned}$$

接下来就可以用快速数论变换了。时间复杂度为$O(\sqrt{n})$。

数论分块记忆化搜索的时间复杂度

考虑这样一道题目，我们定义函数$f(x)=\sum_{i=2}^x f(\lfloor x/i \rfloor)$，特别的我们记$f(1)=0$。之后要求我们计算$f(N)$。其中$1\leq N\leq 10^9$。

根据数论分块的知识，我们知道总共只有$O(\sqrt{N})$个状态需要计算和保存，但是中间的计算量是多大的。一个粗略的估计是$O(N)$，因为每个状态的计算量最多为$O(\sqrt{N})$，总共有$O(\sqrt{N})$个状态。

但是如果仔细观察可以发现时间复杂度会更加优秀。记$L=\lfloor\sqrt{N}\rfloor$，我们可以发现总共涉及的状态可以分为两类：

• 小于等于$L$的：$1,2,\ldots,L$
• 大于等于$L$的：$\lfloor N/1 \rfloor,\lfloor N/2 \rfloor,\ldots,\lfloor N/L \rfloor$

前者每个状态的计算时间复杂度的上界为$O(\sqrt{L})$，总的计算时间复杂度为$O(L\sqrt{L})=O(N^{3/4})$。

后者总的计算时间复杂度的总和可以用积分拟合：

$$\begin{aligned} \int_1^L \sqrt{N/x} \mathrm{d}x &= [2\sqrt{Nx}]_1^L\\ &=O(N^{3/4}) \end{aligned}$$

因此总的计算时间复杂度为$O(N^{3/4})$。

提供一些题目

• Ex - Dice Product 2

最小立方倍数问题

给定$n=10000$个数$a_1,a_2,\ldots, a_n$，每个数的范围是$[1,10^{12}]$，要求为每个数$a_i$计算其最小的立方倍数（即$a_i|y^3$）。

这里有一个$O(10^{6}+n\cdot10^4)$的解法。

对于任意数$x\in [1,10^{12}]$，要计算其最小立方倍数。记录Norm(x)表示x的没有立方因子的最大因子，记录Pair(x)表示Norm(x)的最小立方倍数。我们可以先找到所有x的素数因子$p\in [1,10^{12/3}]$。之后利用这些因子可以得到$Norm(x)$。问题在于如何计算$Pair(x)$呢。

考虑数$Norm(x)$除去所有小于$10^{12/3}$的素因子后，最后剩下的数$s$，数$s$可能有三种情况：

1. s是一个素数或1
2. s是两个不同的素数的乘积
3. s是某个素数的平方

对于第一和第二种情况，我们可以直接得出$Pair(s)=s^2$，而对于第三种情况，有$Pair(s)=\sqrt{s}$。

这样假如我们预先处理出所有不超过$10^{12/2}$的素数，并计算出他们的平方。那么我们可以在$O(10^{12/3})$时间复杂度内计算$Pair(x)$和$Norm(x)$。

我们记$Cubic(x)$表示x的最小立方倍数，那么可以得出：$Cubic(x)=x\cdot Pair(x)$。

这里的总的时间复杂度为$O(10^{6}+n\cdot10^4)$。

积性函数

对于定义于正整数集合上的函数$f$，如果对于任意两个互质的正整数$a$，$b$，有$f(ab)=f(a)f(b)$，则称函数$f$为积性函数。

完全积性函数

对于定义于正整数集合上的函数$f$，如果对于任意两个正整数$a$，$b$，有$f(ab)=f(a)f(b)$，则称函数$f$为完全积性函数，完全积性函数一定也是积性函数。

莫比乌斯函数

下面不讲原理，要看原理可以读《组合数学》这本书。

莫比乌斯函数定义为

$$\mu(x)=\left\{ \begin{array}{ll} 1 & ,x=1 \\ (-1)^k & ,x=p_1\ldots p_k,i\neq j \Rightarrow p_i\neq p_j \\ 0 & ,x=other \end{array} \right.$$

容易发现莫比乌斯函数是积性函数。可以通过线性筛以线性时间复杂度预先算出。

下面说明莫比乌斯函数的主要用处：

$$[g=1]=\sum_{d|g}\mu(d)$$

利用莫比乌斯函数还可以实现莫比乌斯反演，反演公式如下：

$$F\left(n\right)=\sum_{d|n}^{}{f\left(d\right)}\Leftrightarrow f\left(n\right)=\sum_{d|n}^{}{\mu\left(\frac{n}{d}\right)F\left(d\right)}\\ F\left(n\right)=\sum_{n|d}^{}{f\left(d\right)}\Leftrightarrow f\left(n\right)=\sum_{n|d}^{}{\mu\left(\frac{d}{n}\right)F\left(d\right)}$$

莫比乌斯反演也可以用在集合上，公式如下：

$$F(S)=\sum_{T\subseteq S} f(T)\Leftrightarrow f(S)=\sum_{T\subseteq S} (-1)^{|S|-|T|} F(T)$$

乘法逆元

$x$的乘法逆元是指这样的一个数$y$，满足$x\cdot y=1$。如果乘法满足结合律，那么$x$的乘法逆元是唯一的，假设$z$也是$x$的乘法逆元，那么$y=y(xz)=(yx)z=z$。

一般乘法逆元在素数的剩余类域中比较有用，因此下面仅讨论在模素数$p$意义下的乘法逆元。

如果仅想获得少数数的乘法逆元，可以利用费马小定理，由于$x^{p-1}=1$，因此乘法逆元为$x^{p-2}$。这里幂运算可以利用快速幂运算的技巧，因此时间复杂度为$O(log_2p)$。

如果不能保证p是素数，但是能保证x与p互质，那么可以利用扩展欧几里得算法，获得公式

$$ax+bp=1\rightarrow ax=1(\pmod p)$$

而扩展欧几里得算法的时间复杂度为$O(\log_2p)$。

如果想要获得$1,2,\ldots,n$的乘法逆元，如果用上面的算法，需要$O(n\log_2p)$的时间复杂度。但是利用一些简单的性质，我们就可以得到乘法逆元的递推公式，将时间复杂度优化到$O(n)$。设$k=\left\lfloor{p/x}\right\rfloor$，记$r=p(\pmod x)$，可以得出$p=kx+r$。

$$p=kx+r\\ \rightarrow kx+r=0(\pmod p)\\ \rightarrow r^{-1}x+k^{-1}=0(\pmod p)\\ \rightarrow r^{-1}+x^{-1}k^{-1}=0(\pmod p)\\ \rightarrow x^{-1}=-kr^{-1}(\pmod p)\\$$

由于$r<x$，因此可以通过已知逆元$r^{-1}$推导出未知逆元$x^{-1}$。

一些环上定长位移问题

问题1：考虑有长度为$m$的环，环上的点记作$0,1,2,\ldots, m - 1$，你一开始站在位置0，你每次都可以向前移动$a$步，问你可以最终访问到哪些点

我们能访问的点为$at\pmod m$，其中$a\geq 0$，我们知道模运算实际上等同于减法运算，因此可以访问的点为$at-km$。考虑$a$和$m$的最大公约数$g$会发现$g|at-km$，由于扩展欧几里得原理告诉我们一定能到达$g$，因此可以推出所有$g$的倍数的点都可以被访问到。

问题2：考虑有长度为$m$的环，环上的点记作$0,1,2,\ldots, m - 1$，你一开始站在位置0，你每次都可以向前移动$a_1,a_2,\ldots, a_n$步，问你可以最终访问到哪些点

这个问题实际上就是上面问题的扩展，我们可以抵达的顶点是满足$c_1a_1+c_2a_2+\ldots + c_na_n\pmod m=c_1a_1+c_2a_2+\ldots + c_na_n-km$的顶点，记$g=gcd(a_1,a_2,\ldots,a_n,m)$，显然我们只能访问$g$的倍数，并且扩欧保证了一定可以抵达$g$，因此可以访问所有$g$的倍数顶点。

问题3：一周有$d$天。有一副无向图$G$，其中包含$n$个顶点，记作$1,2,\ldots,n$，我们每一天都需要从所在的顶点移动到一个相邻顶点（由无向边连接）。我们从顶点$1$在一周的第$1$天出发，问回到顶点$1$可能在一周的哪些天。

首先我们只需要考虑顶点1所在的连通分量即可，之后都假设图$G$仅包含一个连通分量，且连通分量至少有两个顶点。首先我们可以在两个顶点之间不断来返，这样我们得到了一个回到原点的周期$2$，同时假如存在奇数长度的环，那么我们一定可以得到一个回到原点的奇数周期$2k+1$。之后利用问题2的结论可以得出，允许在顶点1度过的日子为$gcd(2,2k+1,d)$（如果没有奇数环则为$gcd(2,d)$）的最大公约数。

问题4：一周有$d$天。有一副有向图$G$，其中包含$n$个顶点，记作$1,2,\ldots,n$，我们每一天都需要从所在的顶点移动到一个相邻顶点（由有向边连接）。我们从顶点$1$在一周的第$1$天出发，问回到顶点$1$可能在一周的哪些天。

这里我们只需要考虑包含1的强连通分量即可。下面我们假设图中仅包含一个强连通分量。很显然我们要做的就是求出所有从包含$1$的环的长度。如果图中的环的数目只有一个，这个方式是最佳的。否则可以建立$nd$个状态，状态$(i,j)$表示是否可能在一周的第$j$天抵达$i$，之后搜索即可。时间复杂度为$O(nd)$

问题5：一周有$d$天。有一副有向图$G$，其中包含$n$个顶点，记作$1,2,\ldots,n$，我们每一天都需要从所在的顶点移动到一个相邻顶点（由有向边连接）。我们从顶点$1$出发。之后回答$Q$个询问，询问的内容为如果我们如果出发日为$s$，是否有可能在第$j$天出现在顶点$i$

首先我们可以先解决问题4，这样我们可以得到我们可能出现在1的时间，由于这些时间中最小的数（除了0外）即为所有强连通分量的最小公约数$g$，之后我们简单记录一下每个顶点距离$1$的最短距离，记第$i$个顶点的距离为$p_i$。那么对于询问$(s,i,j)$，我们只需要判断$j-(s+p_i)\pmod d$是否能整除$g$即可。

问题6：考虑有长度为$m$的环，环上的点记作$0,1,2,\ldots, m - 1$，你一开始站在位置0，你每次都可以向前或向后移动$a_1,a_2,\ldots, a_n$步，问你可以最终访问到哪些点

与问题2类似，只不过加入了向后移动。向后移动$k$步等价于向前移动$m-k$步，现在我们有$2n$个向前移动的方案。用问题2的方式解决即可。

倍数和约数加总及还原技巧

容斥原理统计倍数出现次数及还原

有一个数组$a_1,a_2,\ldots, a_n$。现在我们需要构建另外一个序列$b_1,b_2,\ldots, b_n$，其中$b_i=\sum_{i|j}a_j$。

这个问题很容易让人联想到快速沃什尔变换的或运算版本。那么这个问题是否能同样在$O(n\log_2n)$的时间复杂度内完成呢？答案是可以的，我们可以为每个下标暴力枚举其倍数并加和，总的时间复杂度为$O(\frac{n}{1}+\frac{n}{2}+\ldots +\frac{n}{n})=O(n\ln n)$。

现在考虑给定了$b$序列，我们是否能从$b$序列还原出$a$序列呢。事实上，也是可以的，注意到$a_n=b_n$，那么假设我们已经还原了$a_{k+1},a_{k+2},\ldots, a_n$，现在我们要还原$a_k$。容易发现$b_k=\sum_{k|j}a_j\Rightarrow a_k=b_k-a_{2k}-a_{3k}-\ldots$。暴力统计即可，时间复杂度也是$O(n\ln n)$。

容斥原理统计约数出现次数及还原

有一个数组$a_1,a_2,\ldots, a_n$。现在我们需要构建另外一个序列$b_1,b_2,\ldots, b_n$，其中$b_i=\sum_{j|i}a_j$。

从$a$到$b$非常容易，我们暴力枚举每个数$x$的倍数$kx$，之后将$x$的值贡献给$kx$即可。总的时间复杂度为$O(n\ln n)$。

那么从$b$到$a$呢，很显然$a_1=b_1$，假设我们已经知道$a_1,a_2,\ldots, a_{k-1}$，要计算$a_k$，容易发现$b_k=\sum_{j|k}a_j\Rightarrow a_k=b_k-\sum_{j|k\land j<k}a_j$。从下到上枚举倍数贡献即可，时间复杂度也是$O(n\ln n)$。

统计带修改的倍数出现次数及还原

现在考虑有一个长度为$n=10000$的序列$b_1,b_2,\ldots, b_n$，其中$b_i=\sum_{i|j}a_j$。我们需要处理$m=10000$次请求，每次修改某个$b_i$，或者对于某个$i$，查询$a_i$。

这个有点像BIT哦。我们不能每次请求都利用容斥将$b$序列转换$a$序列，这样的时间复杂度为$O(nm\log_2n)$，我们需要在$O(nm)$时间复杂度内完成。

一种简单的技术就是使用莫比乌斯反演来实时计算$a_i$。提前计算出莫比乌斯函数$\mu$，之后利用公式$b_i=\sum_{i|j}a_j$可以推出$a_i=\sum_{i|j}\mu(\frac{j}{i})b_j$。这样每次计算的时间复杂度为$O(n)$。

这边顺带一提，另外一个从$a$到$b$的问题：一个长度为$n=100000$的序列$a_1,a_2,\ldots, a_n$，其中$b_i=\sum_{i|j}a_j$。我们需要处理$m=100000$次请求，每次修改某个$a_i$，或者对于某个$i$，查询$b_i$。

实际上我们提前维护好每个数的约数信息，而一个数$x$的约数最多有$2\sqrt{x}$，因此修改$a_i$的时候，只需要将所有$i$的约数$j$所代表的的$b_j$同步修改掉即可。这样每次修改的时间复杂度为$O(\sqrt{n})$，而每次查询的时间复杂度为$O(1)$。

统计带修改的约数出现次数及还原

现在考虑有一个长度为$n=10000$的序列$b_1,b_2,\ldots, b_n$，其中$b_i=\sum_{j|i}a_j$。我们需要处理$m=10000$次请求，每次修改某个$b_i$，或者对于某个$i$，查询$a_i$。

提前计算出莫比乌斯函数$\mu$，之后利用公式$b_i=\sum_{j|i}a_j$可以推出$a_i=\sum_{j|i}\mu(\frac{i}{j})b_j$。这样每次计算的时间复杂度为$O(n)$。

顺带一提，另外一个从$a$到$b$的问题：一个长度为$n=100000$的序列$a_1,a_2,\ldots, a_n$，其中$b_i=\sum_{i|j}a_j$。我们需要处理$m=100000$次请求，每次修改某个$a_i$，或者对于某个$i$，查询$b_i$。

这个问题需要我们使用分段处理的技术。对于一个数$x<\sqrt{n}$，我们为其维护$a_x$信息。而对于数$y\geq \sqrt{n}$，我们为其维护一个$b_i'$信息。当我们修改一个数$x$的时候，我们直接修改$a_x$，而当我们修改$y$的时候，由于其最多有$\sqrt{n}$个倍数，所以，保留枚举所有的倍数$ky$，并修改$b_{ky}'$即可。对于查询$b_t$，其值由两部分组成，一部分是所有小于$\sqrt{n}$的约数，一部分是大于等于$\sqrt{n}$的约数，前者我们暴力枚举$a_1,a_2,\ldots,a_{\sqrt{n}}$统计即可，后者已经记录在$b'_t$中了。因此不管是查询还是修改，时间复杂度都是$O(\sqrt{n})$。

最多k个不同数字组成的n的倍数

问题1：给定某个正整数$n$，找到某个$n$的倍数$m$，要求$m\geq n$且$m$的每个十进制位中只有最多$k$个不同的数字。其中$n\leq 10^4$

这个问题非常奇妙的一点，就是利用了${10\choose k}\leq {10\choose 5}=210$。因此我们可以枚举所有$0,1,\ldots, 9$的大小为$k$的子集，并利用它构造一个$n$的倍数。

$m$是$n$的倍数，另外一个等价的含义就是$m$除上$n$的余数为$0$。

利用这一点，我们可以直接用最短路来实现。我们建立$n$个顶点，第i个顶点对应模上$n$的余数为$i-1$，之后将转移关系建立边，从起点跑最短路即可。

问题2：给定某个正整数$n$，找到某个$n$的倍数$m$，要求$m\geq n$且$m$的每个十进制位中只有最多$4$个不同的数字，且$m$的长度正好为$L$，其中$n\leq 10^{12}$，$L=100$。

神奇的问题，可以去大佬Youtube上面的讲解。首先我们构造多个长度正好为$L$的仅有$0$和$1$组成的数字，并将其对$n$的余数保存到哈希表中。由生日悖论知道我们最多只需要$O(\sqrt{n})$个串就会发生一次碰撞。假设碰撞的两个值分别为$a$和$b$，我们可以证明$a-b$一定是$n$的倍数，且其中仅包含四个数字$0,1,8,9$。如果位数不够我们可以在后面补充上$0$即可。

n的因子中最长反链

考虑所有n的因子，我们在其上定义偏序关系，如果$a|b$，那么记作$a\leq b$。现在我们希望能得到n的因子中的最长反链。

我们可以利用匹配算法来求最大反链，时间复杂度为$O(\sqrt{n}m)$，其中n是因子数，m是因子之间的偏序关系数量。但是如果n非常大的话，这个算法就不能用了。

有一个简单的结论，对于数$x=p_1^{c_1}p_2^{c_2}\ldots p_k^{c_k}$，这里$p_i$是互不相同的素数，我们定义$x$的度数为$deg(x)=c_1+c_2+\ldots+c_k$。很显然度数相同的数之间不可能存在整除关系，因此度数为某个特定数的所有数都可以组成一条反链。而n的因子中最长反链可以由所有度数正好为$\left\lfloor \frac{deg(n)}{2} \right\rfloor$的因子组成。

我们可以利用分治+FFT算法高效算出反链的长度。

1到n取k个数的可能的和

在$1,2,\ldots,n$中取k个数，问有多少可能的和。事实上我们知道可能的和的下界为$L=1+2+\ldots+k$，而上界为$R=(n-k+1)+\ldots+n$。现在我们证明$[L,R]$之间的数都能取到。

实际上假设我们有k个指针，一开始分别指向$1,2,\ldots,k$。这时候和为$L$。接下来我们每次选择可以右移动的指向最靠右的指针，将其右移一步。很显然每一次移动k个指针指向的数的和都会增加1，而且这个流程直到所有指针分别指向$(n-k+1),\ldots, n$才会结束，即总和达到了$R$，因此我们就证明了$L$和$R$之间的每个数都可以取到。

离散对数

今天做了一道cf的题目，发现原来还有离散对数这么一个玩意，简单记录一下。

问题1：已知自然数$a,b,p$，其中$a$与$p$互质，求一个自然数$x$，使得$a^x=b\pmod p$。

由于$a$生成的循环群 $\\{a^0,a^1,a^2,\ldots\\}$ 的大小一定不会超过$p$，因此我们仅需要考虑$0\leq x\leq p-1$。我们可以利用BSGS算法来计算。记$k=\sqrt{p}$，我们提前计算$a^0,a^1,\ldots,a^k$，并将其存入哈希表中。由于假如$x$存在，那么记$i=\left\lfloor \frac{x}{k}\right\rfloor$，$j=x \pmod k$，满足$x=ik+j$。代入公式得到$a^{ik+j}=b\Rightarrow a^{j}=ba^{-ik}$。我们可以直接算出$ba^{-ik}$（由于$a$与$k$互质，可以利用扩欧得到$a^{-1}$）并拿到哈希表中查找是否出现即可。

这样我们预处理的时间复杂度为$O(\sqrt{p})$，之后计算对数时暴力枚举的时间复杂度为$O(\sqrt{p})$。

问题2：已知自然数$x,b,p$，其中$p$是一个素数，求一个自然数$a$，满足$a^x=b\pmod p$。

由于素数一定有原根，我们可以找到它的原根$g$。由于原根的幂运算得到的集合大小为$p-1$，可以涵盖$[1,p-1]$之间的所有数。所以我们可以保证每个非0的数都可以表示为$g$的幂次。现在我们代入公式得到：

$$a^x=b \pmod p\\ \Rightarrow (g^{\log_gx})^a=g^{\log_gb}\pmod p\\ \Rightarrow g^{x\log_ga}=g^{\log_gb}\pmod p\\ \Rightarrow x\log_ga=\log_gb \pmod p-1\\ \Rightarrow x\log_ga+k(p-1)=\log_gb$$

最后一项，我们可以用扩欧计算$x$与$p-1$的最大公约数$t$，如果$t$不能整除$\log_gb$，则无解，否则就可以利用扩欧直接得到$\log_ga$，之后用快速幂$a=g^{\log_ga}$。这里仅用到了离散对数算法和扩展欧几里得算法，时间复杂度为$O(\sqrt{p}+\log_2p)$。

问题3：已知自然数$x,b,p$，其中$p$是一个素数，求所有可能的自然数$a$，满足$a^x=b\pmod p$且$a<p$。

首先我们可以用问题2的方式得到一个解$a_0$，记$g$是$p$的一个原根。

由于$g$是原根，因此

$$a^x=b=a^x_0 \pmod p\\ \Rightarrow xlog_ga=x\log_g a_0 \pmod p-1\\ \Rightarrow xlog_ga=x\log_g a_0+k(p-1)\\ \Rightarrow log_ga=\log_g a_0 + \frac{k(p-1)}{x}$$

很显然上面公式有解，前提条件是$\frac{x}{gcd(p-1,x)}|k$，因此我们可以记$k=i\frac{x}{gcd(p-1,x)}$，那么有$log_ga=\log_g a_0 + i\frac{(p-1)}{gcd(p-1,x)}$。因此我们可以枚举$i$得到所有的解。

问题4：已知自然数$a,b,p$，求一个自然数$x$，使得$a^x=b\pmod p$

这个问题非常类似于问题1，但是区别在于$a$与$p$不一定互质。记$d_1=gcd(a,p)$，那么公式变成：

$$\frac{a}{d_1}a^{x-1}=\frac{b}{d_1}\pmod \frac{p}{d_1}$$

如果$a$和$\frac{p}{d_1}$依旧不互质，我们可以继续取最大公约数并化简公式，设最后得到的公式为：

$$\frac{a^k}{D}a^{x-k}=\frac{b}{D} \pmod \frac{p}{D}$$

我们上面的公式只能计算$\geq k$的结果$x$，因此我们需要手动暴力枚举$x=1,2,\ldots,k-1$，试一试是不是有可行的。如果都不可行，那么如果$b$不能整除$D$，那么一定不会有$\geq k$的结果。否则我们将$\frac{a^k}{D}$取逆乘到右边去（此时$\frac{a^k}{D}$与$\frac{p}{D}$一定互质），问题就化成了问题1，求解即可。总的时间复杂度为$O(\sqrt{p}+\log_2p)$。

最小分母分子

问题1：给定两个分数$\frac{b}{a}$和$\frac{d}{c}$，其中$0\leq \frac{b}{a} \leq \frac{d}{c}$，求一个分数$\frac{y}{x}$满足$\frac{b}{a}\leq \frac{y}{x}\leq\frac{d}{c}$，如果有多个，就求出其中分母最小的，如果有多个，就求出其中分子最小的。

我们先证明一个结论，设$x'$是所有满足条件的分数中的最小分母，而$y'$是所有满足条件的分数中的最小分子，那么$\frac{b}{a}<\frac{y'}{x'}<\frac{d}{c}$。设$\frac{y_0}{x'}$和$\frac{y'}{x_0}$是区间内的分数，那么有：

$$\frac{b}{a}\leq \frac{y'}{x_0} \leq \frac{y'}{x'} \leq \frac{y_0}{x'} \leq \frac{d}{c}$$

因此结论得到证明。

现在记$L = \left\lceil \frac{b}{a} \right\rceil$，$R = \left\lfloor \frac{d}{c} \right\rfloor$。如果有$L\leq R$，那么我们可以取$y=L,x=1$就可以同时取到最小分母和最小分子了。

如果$L>R$，那么就意味着有$L-1<\frac{b}{a}\leq \frac{d}{c} < L$。我们可以从所有数中同时减去整数$L-1$，可以得到：

$$\frac{b-(L-1)a}{a}\leq \frac{y-(L-1)x}{x}\leq \frac{d-(L-1)c}{c}$$

现在问题变成了处理解决$\frac{b'}{a'}\leq \frac{y'}{x'} \leq \frac{d'}{c'}$，其中左右边界都是真分数。我们需要找到满足该不等式的最小分子$y'$和分母$x'$，这时候一定有原问题的最小分子为$y'+(L-1)x'$，而最小分母为$x'$。这是显然的，我们只是从原问题中减去了某个整数。

之后我们考虑将公式求反，我们通过求解$\frac{c'}{d'}\leq \frac{x'}{y'} \leq \frac{a'}{b'}$来找到最小分子和最小分母，由于最小分子和最小分母是同时取得的，因此很显然在这个不等式下求得的解中的最小分母就是原问题的最小分子，而最小分子就是原问题的最小分母。

这里有一个小坑，就是当$d'=0$的时候，我们不能颠倒左边的边界，但是此时问题变得非常简单，$0\leq \frac{y'}{x'}\leq \frac{d'}{c'}$，我们可以得出$y'=1$，而$x'=\left\lceil \frac{c'}{d'} \right\rceil$。

这个算法与辗转相除法类似，每次递归的时候都会使得分母减少至少一半，因此总的时间复杂度为$O(\log_2abcd)$。随便写写就好了。

问题2：给定素数$p$，找到某个分数$\frac{y}{x} = n \pmod p$，其中$0\leq y<x<p$，如果有多个，则要求分母最小，如果还有多个，则要求分子最小。

由于分母一旦决定，分子也就被决定了，因此这里我们只需要保证分母最小即可。化简一下，可以得出

$$\frac{y}{x}=n\pmod p\\ \Rightarrow y=xn\pmod p\\ \Rightarrow y=xn-kp\\$$

这里我们将约数条件代入，可以得出：

$$0\leq y=xn-kp < x < p\\ \Rightarrow \frac{p}{n}\leq \frac{x}{k} \leq \frac{p}{n-1}$$

这里我们无需关心$k=\left\lfloor \frac{xn}{p} \right\rfloor$，因为上面的不等式已经包含了这个条件。现在我们只需要找到区间内有着最小的分子和分母的分数即可。这个实际上就是问题1了。

提供一道原题。

公约数公倍数问题

一些约定：

• $\phi(x)$表示$x$的不同素因子数目。

• $\Phi(x)$表示$x$的因子数目。

问题1：给定一组数$a_1,\ldots, a_n$，之后处理$m$个请求，第$i$个请求请求给定$x_i$，要求找出序列中与$x_i$互质的数的数目（即最大公约数为1）。满足$1\leq a_i,n,m,x_i\leq M=300000$

我们记$f(x)=\sum_{i=1}^n[x\mid a_i]$，即序列中有多少数是$x$的倍数。

之后要统计序列中有多少数是与$x$是互质的，我们可以使用容斥定理，记录$A_i$表示能整除$i$的序列中所有数组成的集合，那么结果就是

$$|\bigcap_{d\mid x}\overline{A_d}|$$

容斥的时间复杂度是$O(2^{\phi(x)})$，其中$\phi(x)$表示$x$的不同素因子数目。

还有一种方法就是借助莫比乌斯函数：

$$\sum_{i=1}^n[gcd(a_i,x)=1]\\ =\sum_{i=1}^n\sum_{d\mid gcd(a_i,x)}\mu(d)\\ =\sum_{d\mid x}\mu(d)\sum_{i=1}^n[d\mid a_i]\\ =\sum_{d\mid x}\mu(d)f(d)$$

莫比乌斯函数的时间复杂度为$O(\Phi(x))$,其中$\Phi(x)$表示$x$的因子数目。

一般情况下容斥会快于莫比乌斯函数，因为不同素因子数目一般会非常小，比如对于$300000$以内的数，因子数最多可以达到$180$个，而不同素因子最多只有$6$个。而对于$10^{18}$以内的数，因子数最多可以达到$103680$，而不同素因子最多仅$15$个。

算法的总的时间复杂度为$O(M\ln M+\sum_{i=1}^m2^{\phi(x_i)})$。还是非常快的。

问题2：给定一组数$a_1,\ldots, a_n$，其中$1\leq a_i,n\leq M=300000$。要求找到最小的一个非空子集，使得子集中的的所有数的最大公约数为1。输出子集的大小。

这是CF的原题。

容易想到DP的方式，记录$dp(i)$表示最大公约数为$i$的因子的最小子集大小。注意到只有满足$i\mid j$，$dp(j)$才能对$dp(i)$产生贡献，所以我们需要遍历所有这样的$j$。现在只剩下一个问题了，怎么判断是否存在一个数$a_k$，使得$gcd(a_k,j)\mid i$。

我们可以发现，由于$a_i\leq M=300000$，而所有不超过$M$的正整数，最多有6个不同的素因子。因此我们可以提前计算出$1$到$M$中每个数的素因子，以及每个数的倍数在$a$序列中出现多少次。之后我们构造一个函数$g$，$g(i)$表示$a$序列中存在多少个数与$i$拥有大于1的公约数。函数$g$可以利用问题1的方式计算出来。

利用我们之前搞出来的$g$，就可以判断是否存在这样的$a_k$了。$a_k$存在，那么$a$序列中就必定存在至少一个数，与$j/i$互质，即$g(j/i)<n$。

总的时间复杂度为$O(M\ln M+\sum_{i=1}^m2^{\phi(x_i)})$。

问题3：给定一组数$a_1,\ldots, a_n$，要求找到两个数（两个数允许值相同，但是下标不能相同），要求这两个数互质。其中$a_i,n\leq M=300000$。

我们可以记录$f(x)=\sum_{i=1}^n[x\mid a_i]$，即序列中有多少数是$x$的倍数，并动态维护它。

之后我们遍历$a$序列，假设遍历到$a_i$，我们可以利用容斥以及函数$f$快速判断已经扫描过的数有多少数与$a_i$互质，如果存在，我们可以用$a_i$与$a_j(j<i)$计算最大公约数，直到找到互质的数为之。否则我们就动态修改函数$f$。每次容斥花费的时间为$2^{\phi(a_i)}$，而找互质的数的时间复杂度不会超过$n\log_2M$，每次动态修改$f$的时间复杂度为$\Phi(a_i)$。

总的时间复杂度为$O(n\log_2n+M\ln M+\sum_{i=1}^n2^{\phi(a_i)})$。

问题4：给定一组数$a_1,\ldots, a_n$，要求找到两个不同的元素（值允许相同，但是下标必须不同），使得它们的最大公约数最大。其中$a_i,n\leq M=300000$。

我们可以记录$f(x)=\sum_{i=1}^n[x\mid a_i]$，即序列中有多少数是$x$的倍数，在计算这个的同时，我们为每个数维护一个大小为2的堆，将前两个贡献的数记录在堆中。

这样我们只需要从大到小遍历约数$x$，如果$x$的倍数出现的次数不少于2（$f(x)\geq 2$），那么我们就找到了所需的最大公约数，同时从堆中弹出两个顶部元素即可。

问题5：给定一组数$a_1,\ldots, a_n$，要求找到两个数（允许值相同，但是下标不允许相同），使得它们的最大公约数最小。其中$a_i,n\leq M=300000$。

问题2提出的DP实际就可以直接解决这个问题。我们只需要找到满足最小集合大小不超过$2$的所有可以构成的集合最小公约数中最小的那个即可，记这个数为$g$。

之后如何找到最大公约数为$g$的数呢，我们仅考虑$a$序列中能整除$g$的数，将它们都除去$g$后，我们要找的就是其中两个互质的数，这就是问题3。

问题6：给定一组数$a_1,\ldots, a_n$，要求找到两个不同的元素（值允许相同，但是下标必须不同），使得它们的最小公倍数最大。其中$a_i,n\leq M=300000$。

CF原题

我们可以通过枚举最大公约数来找最大公倍数。

考虑最大公约数为$g$时，我们只需要考虑序列中那些能整除$g$的元素，我们将这些元素提取出来，并都除去$g$，现在我们要做的就是在这些被提取出来的元素中，找到乘积最大的互质的数即可。

通过问题3我们已经知道怎么找一对互质的数了，现在我们修改问题3提出的方法解决这个问题。

方法就是我们从大到小遍历元素，尝试对于每个元素，找到最大的与其互质的元素。具体做法，我们可以维护一个栈，每次扫描到新的元素$a_i$，我们就利用动态维护的倍数统计函数$f$和容斥检查一下栈中是否有元素与其互质，如果存在，就不断退栈，直到栈中不再存在与$a_i$互质的元素为止，同时我们计算$a_i$与栈中最大互质元素$y$的最大公倍数（二者的乘积再乘上$g$）。最后我们将$a_i$加入到栈中。当然在退栈的过程中，有一些没有找到对应的互质的数也可能会被弹出掉，但是它们实际上已经对最终结果没有影响了（与其互质的数必定小于$a_i$，且其本身又小于$y$，因此它的最大公倍数已经不会影响结果了）。

算法的总的时间复杂度为$O(M\ln M + \sum_{i=1}^n 2^{\phi(a_i)}\Phi(a_i))$

问题7：给定一组数$a_1,\ldots, a_n$，要求找到两个不同的元素（值允许相同，但是下标必须不同），使得它们的最小公倍数最小。其中$a_i,n\leq M=300000$。

类似于问题6，我们只需要修改算法，让算法从小到大遍历元素即可。

问题8：给出一组数$a_1,\ldots,a_n$，其中$1\leq a_i\leq 10^{12}$，且$n\leq 10^6$。要求找到另外一个序列$b_1,\ldots,b_n$，满足$1\leq b_i$且$gcd(b_1,\ldots,b_n)>1$，称$\sum_{i=1}^n\mid b_i-a_i\mid$为序列$b$的费用，要求序列$b$的费用最小。如果有多个序列满足要求，任意输出一个序列即可。

问题要求我们找到一个素数，要求修正$a_i$为每个素数的倍数。可以很容易想到选择素数2，这时候得出序列$b$的序列一定不会超出$n$。

现在假设$b'$是费用最小的序列，现在我们发现至少有一半的数，对费用的贡献不超过1（否则费用就会超出$n$）。

于是我们可以选择找出任意一个对费用贡献不超过1的数，记作$x$，找到$x-1$、$x$、$x+1$的所有素因子，然后尝试找出最优解。

每一次我们都有$1/2$的概率得到最终结果。重复这个过程$100$次，结果错误的概率仅为$2^{-100}$，完全可以忽略不计。

提供一道题目。

问题9：给定$n$个正整数$a_1,\ldots,a_n$，每个数的均不超过$M=10^{18}$，要求求最大公约数。其中$n\leq 10^8$

需要注意到如果$a,b$彼此没有整除关系，那么一定有$gcd(a,b)<a,b$。因此我们维护前$k-1$个数的最大公约数$g$，现在要求前$k$个数的最大公约数，我们先校验一下$a_n$和$g$之间是否有整除关系，如果没有就跑一次欧几里得算法。可以知道欧几里得算法最大只会执行$\log_2M$次（但是这里会发现由于$g$是递减的，因此欧几里得算法总共占用的时间为$O(\log_2M)$），总的时间复杂度为$O(n+\log_2M)$

问题10：给定集合$S=\{1,\ldots, n\}$，对于任意$S$的大小至少为$2$的子集$C$，其权值为$W(C)=\max\{gcd(a,b)|a\neq b\land a,b\in C\}$。现在给定$K\geq 2$，要求找到大小正好为$K$且权值最小的子集并输出。这里$n\leq 10^6,2\leq K\leq n$。

假设最终集合为$T$，且存在某个数$b\in T$，且$b$的某个约数$a$不在集合$T$中，那么我们可以用$a$替换$T$中的$b$。这个观察给了我们贪心算法正确性的保证。

可以发现对于最终集合$T$，如果$x\in T$是$T$中最大真因子最大的数，且记$x$的最大真因子为$y$。那么由于$y$已经存在于$T$中了，因此$W(T)\geq gcd(x,y)=y$。且由于没有任何数的最大因子超过$y$，因此就可以保证$W(T)=y$（两个不同数的最大公约数一定是某个数的真因子）。

上面的内容其实可以总结为任意一个集合中不同元素的最大公约数都不会超过集合中某个数的最大真因子。

现在我们知道了集合的权值最小，当且仅当集合中每个数的最大因子的最大值最小。这里我们可以设计一个漂亮的贪心过程：首先将所有数按照其最大真因子从小到大排序（这一步可以$O(n\log_2n)$完成）。之后我们取最大真因子最小的$K$个数组成集合。

这里还有一个疑问，我们组成的集合是否能保证一个数存在于集合中，其所有因子也都存在呢。这是一定的，因为一个数的最大真因子一定大于其任意因子，因此其因子一定早于这个数之前被加入到了集合中。

到此，算法结束。

提供一道题目。

取模运算的一些问题

设$a$为非负整数，$b$为正整数，那么一定有$a=kb+c$，其中$0\leq c<b$，$k=\left\lfloor\frac{a}{b}\right\rfloor$。我们记$c=a\pmod b$。

取模运算有一些比较有用的性质：

• 对于任意非负整数$x$，以及两个正整数$0<a<b$，一定有$(x\pmod a)\pmod b=x\pmod a$
• 对于任意正整数$x$，以及某个正整数$a\leq x$，一定有$x\pmod a<\frac{x}{2}$。

题目1：给定两个正整数$a,b$，统计在$1,\ldots,n$中有多少数$x$满足$(x\pmod a)\pmod b=(x\pmod b)\pmod a$

如果$a=b$，则每个数都可以。接下来我们始终假设$a<b$，根据取模运算的特性，可以得出$(x\pmod a)\pmod b=x\pmod a$。

我们将$x$表示为$x=kb+r$，则我们希望找到不同的$(k,r)$对，满足$r=kb+r\pmod a$。这时候显然有$kb=0\pmod a$，即$lcm(a,b)| kb$。我们枚举$k$即可。

时间复杂度为$O(\log_2a+\log_2b)$。

题目2：给定一组正整数$a_1,\ldots,a_n$，定义$f(x,i)=x\pmod a_i+f(x\pmod a_i,i+1)$，且特殊的$f(x,n+1)=0$。要求对于所有非负整数$x$，找到$f(x,1)$的最大值。

记$x_i=x_{i-1}\pmod a_i$，特殊的$x_0=x$，记$ans_i=x_i$。我们可以定义$g(i,j,k)$表示选择第$i$个数$x_i$后，且$x_i$的取值范围为$[0,j)$，则$ans_1+\ldots+ans_i$的值为$i\cdot x_i+k$。我们发现每个三元组$(i,?,?)$可以分解为两个$(i+1,?,?)$，其中有一个三元组的第二维度的值为$a_{i+1}-1$。

我们用DP的方式来减少实际需要的三元组数量，只需要维护$(i,j,k)$，其中满足随着$j$的增加$k$不断减少的三元组。同时可以发现$(i,?,?)$的三元组最多有$i$个。

到此我们给出了一个$O(n^2\log_2n)$时间复杂度的算法。（用平衡树维护三元组）

当然这还不够，我们发现如果$(i,j,?)$中$j<a_{i+1}$，那么我们可以直接保留它到下一个状态，我们只分解那些满足$j\geq a_{i+1}$的三元组。

整个算法的过程中，只会插入$n$个三元组$(i,a_i-1,?)$。其余的三元组都是由它们分解来的，每一次分解，都会使某个三元组的第二个维度至少减少一半，因此总的时间复杂度为$O(n\log_2n\log_2M)$，其中$M=\max(a_1,\ldots,a_n)$。

提供一道题目。

题目3：给定$n$个数$a_1,\ldots,a_n$，定义$f(d)=\sum_{i=1}^n (\left\lceil\frac{a_i}{d}\right\rceil d-a_i)$，要求计算满足$f(d)\leq k$的最大的$d$。其中$a_i\leq 10^9$, $0\leq k\leq 10^{18}$，$1\leq n\leq 100$

我们先稍微转换一下公式：

$$\sum_{i=1}^n (\left\lceil\frac{a_i}{d}\right\rceil d-a_i) \leq k\\ \Rightarrow d\sum_{i=1}^n \left\lceil\frac{a_i}{d}\right\rceil \leq k+\sum_{i=1}^na_i$$

注意到$\left\lceil\frac{a_i}{d}\right\rceil$的取值最多有$2\sqrt{a_i}$种可能性，因此$\sum_{i=1}^n \left\lceil\frac{a_i}{d}\right\rceil$最多有$2n\sqrt{10^9}$种可能性。我们可以用数论分块技术来确定每种可能性$d$的范围。于是最终的时间复杂度为$O(2n\sqrt{10^9}\log_2n)$。

类欧几里德算法

题目1：计算$\sum_{i=0}^n\lfloor \frac{ai+b}{c}\rfloor$，其中仅保证$c>0$，$n\geq 0$。

提供一道题目。

分几种情况讨论：

1. 若$a,b<0$，则将式子转换成$\sum_{i=1}^n-\lceil\frac{-a}{c}\rceil i-\lceil\frac{-b}{c}\rceil+\lfloor \frac{(a\%c)i+(b\%c)}{c}\rfloor$
2. 若$a,b\geq c$，则将式子转换成$\sum_{i=1}^n\lfloor\frac{a}{c}\rfloor i+\lfloor\frac{b}{c}\rfloor+\lfloor \frac{(a\%c)i+(b\%c)}{c}\rfloor$
3. 否则$0\leq a,b\lt c$。记$m=\lfloor \frac{ni+b}{c}\rfloor$，根据下面公式进行转换：

$$\begin{aligned} &\sum_{i=0}^n\lfloor \frac{ai+b}{c}\rfloor\\ =&\sum_{i=0}^n\sum_{j=0}^m[j\leq \lfloor \frac{ai+b}{c}\rfloor]\\ =&\sum_{j=0}^m\sum_{i=0}^n[j\leq \lfloor \frac{ai+b}{c}\rfloor]\\ =&(n+1)+\sum_{j=1}^m\sum_{i=0}^n[j\leq \lfloor \frac{ai+b}{c}\rfloor]\\ =&(n+1)+\sum_{j=1}^m\sum_{i=0}^n[i\geq \lfloor\frac{cj-b+a-1}{a}\rfloor]\\ =&(n+1)+\sum_{j=1}^m(n-\lfloor\frac{cj-b+a-1}{a}\rfloor+1)\\ =&(n+1)m+\sum_{j=0}^{m-1}\lfloor\frac{cj+c-b+a-1}{a}\rfloor \end{aligned}$$

可以发现每一次转换后，$a,c$会变成$c\%a,a$，这实际上类似于欧几里德算法，因此时间复杂度为$O(\log_2a+\log_2c)$。

一些快速计算的技巧

• 一个数能整除$3$当且仅当所有数的和能整除$3$。
• 记$f(x)$表示$x$的所有$k$进制位之和，可以发现$f(x)=x\pmod{k-1}$，故$f^{\infty}(x)=x\pmod{k-1}$，特殊的是如果$k-1\mid x$且$x>0$，则结果为$k-1$。

参考资料

• 原根wiki
• 二次剩余wiki
• 欧拉准则wiki
• 原根oi wiki
• Tonelli-Shanks算法
• 证明Tonelli-Shanks算法的简短博客
• （美）布鲁迪（Brualdi,R.A.）著.组合数学 第4版[M].机械工业出版社,2005:630.
• 欧拉函数 wiki
• 乘法逆元的计算
• BSGS