数论

Published: by Creative Commons Licence

  • Tags:

原根

若正整数a与m互质,由欧拉定理知道存在某个正整数d,满足$a^d=1\mod 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$,下面命题均成立。

下整除结结合性

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

证明:

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

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

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

由于:

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

命题得证。

上整除结合性

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

证明:

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

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

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

由于:

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

命题得证。

上下整除混用

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

证明:

考虑到$\Big\lfloor \frac{a}{bc} \Big\rfloor \leq \Big\lceil \frac{\big\lfloor \frac{a}{b} \big\rfloor}{c}\Big\rceil, \Big\lfloor \frac{\big\lceil \frac{a}{b} \big\rceil}{c} \Big\rfloor \leq \Big\lceil \frac{a}{bc} \Big\rceil$,而$\Big\lfloor \frac{a}{bc} \Big\rfloor + 1\geq \Big\lceil \frac{a}{bc} \Big\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$,让其能被整除。可以证明,我们最多将其增大到$\lceil \frac{x}{d} \rceil d$或减少到$\lfloor \frac{x}{d} \rfloor d$,因为我们每多增大$d$,不如在除$d$后增加$1$的费用低。因此我们给出了一个暴力递归算法。

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

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

一道题目

向下取整数论分块

面对下面这样的函数:

其中$m\leq n$。

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

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

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

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

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

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

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

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

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}$,它们的下整值落在${\lfloor\frac{n}{1}\rfloor,\lfloor\frac{n}{2}\rfloor,\ldots,\lfloor\frac{n}{\sqrt{n}}\rfloor}$,而对于任意,而对于任意$i>\sqrt{n}$,其下整值一定落在${1,2,\ldots,\sqrt{n}}$中。因此可能的下整值最多有中。因此可能的下整值最多有$2\sqrt{n}$种。借此我们得到了时间复杂度的上限。借此我们得到了时间复杂度的上限$O(\sqrt{n})$。

向上取整数论分块

类似于向下取整的版本,问题是求解下面公式:

这里不仔细讨论优化的方式,仅讨论分块的方式。

我们称$\lceil{\frac{n}{i}}\rceil$为$i$的上整值。记上整值为$x$的所有的$i$的集合${i_1,i_2,\ldots,i_k}$为$x$的导出集合,记作$E(x)$。

对于任意$i$,记$j=\lceil\frac{n}{\lceil\frac{n}{i}\rceil}\rceil$,可以推出:$\lceil \frac{n}{i} \rceil < \frac{n}{j-1}$和$\lceil \frac{n}{i} \rceil \ge \frac{n}{j}$。由后者可知$j\leq max(E(\lceil\frac{n}{i}\rceil))$,而由前者可知$\lceil\frac{n}{j}\rceil \leq \lceil\frac{n}{i}\rceil\leq \lceil\frac{n}{j}\rceil$,结合得到$j=min(E(\lceil\frac{n}{i}\rceil))$。

因此代码大概为:

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

最小立方倍数问题

给定$n=10000$个数 ,每个数的范围是 ,要求为每个数 计算其最小的立方倍数(即 )。

这里有一个 的解法。

对于任意数 ,要计算其最小立方倍数。记录Norm(x)表示x的没有立方因子的最大因子,记录Pair(x)表示Norm(x)的最小立方倍数。我们可以先找到所有x的素数因子 。之后利用这些因子可以得到$Norm(x)$。问题在于如何计算$Pair(x)$呢。

考虑数 除去所有小于 的素因子后,最后剩下的数$s$,数$s$可能有三种情况:

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

对于第一和第二种情况,我们可以直接得出 ,而对于第三种情况,有

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

我们记$Cubic(x)$表示x的最小立方倍数,那么可以得出:

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

快速绝对值差计算

考虑有这样一个序列$x_1,x_2,\ldots x_n$,其中每个整数都不超过$10^6$,用这个数列可以唯一确定一个函数$f$,其接受一个参数$x_0$,这个函数会输出:

其代码大概为:

f(x0){
    ans = x0;
    for(int i = 1; i <= n; i++){
		ans = |ans - a[i]|;       
    }
    return ans;
}

现在我们有m个参数$a_1,a_2,\ldots,a_m$,$a_i\leq 10^6$,希望计算这m个输入下f的对应输出$f(a_1),f(a_2),\ldots, f(a_m)$。

其中$n,m \leq 10^6$。

很显然,我们可以在时间复杂度$O(nm)$内解决,但是会花掉过多的时间。

我们可以定义另外n个函数$f_1,f_2,\ldots, f_n$,其中$f_k$表示由序列后k个元素确定的函数,其代码应该为:

fk(x0){
    ans = x0;
    for(int i = n - k + 1; i <= n; i++){
		ans = |ans - a[i]|;       
    }
    return ans;
}

可以发现这n个函数之间具有递推关系:

我们可以将函数用一个数组表示,数组下标为i的元素的值表示输入为i时的输出。

我们自然地定义函数$f_{0}(x)=x$,因此$f_{0}$函数的数组表示为:

[0,1,2,3,4,...,n]

之后考虑函数$f_1$,其数组表示为:

[a[n],a[n]-1,a[n]-2, ..., 1, 0, 1, 2, ..., n - a[n]]

可以发现$f_1$实际上是将$f_0$的某段前缀翻转并放在了最前面,并删除部分的后缀。

同理我们可以推广出$f_i$到$f_{i+1}$的数组形式的变换。

接下来我们考虑如何快速计算出$f_1,f_2,\ldots, f_n$,我们可以递推处理,这里翻转拼接都可以用持久化平衡树(比如treap)来实现。

而$f=f_n$,因此我们也得到了$f$的数组表示,之后的m个请求可以$O(1)$高效处理。总的时间和空间复杂度为$O(n\log_2n+m)$。

积性函数

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

完全积性函数

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

莫比乌斯函数

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

莫比乌斯函数定义为

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

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

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

欧拉函数

欧拉函数$\varphi(x)$表示的是小于x的正整数中与x互质的数的数目,特别的是$\varphi(1)=1$。

欧拉函数的通项公式:

从通项公示中可以得出:

其中$g=gcd(a,b)$。

容易发现欧拉函数是积性函数,因此可以用线性筛直接处理。

欧拉函数的性质有以下两个:

以及如果n与m互质,则有

素数筛

简介

假如我们要筛选出[1,N]之间的所有素数,我们该如何实现?下面列举几种实现方式

暴力法

prime = []
for(i = 2; i <= N; i++)
    boolean flag = true
    for(j = 2, until = sqrt(i); j <= until; j++)
        if(i % j == 0)
        {
            flag = false;
            break;
        }
	if(flag)
        prime.add(i)

对于每个可能的素数i,由于如果i是一个合数,则必定可以写作i=ab,其中a或b至少一者不超过sqrt(i)。因此对于每个素数的判断时间复杂度最多为O(sqrt(N)),总的时间复杂度上界确认为O(N*sqrt(N))。

筛法

prime = []
isComposite = [1,N] filled with false
for(i = 2; i <= N; i++)
    if(isComposite[i])
        continue
    prime.add(i)
    for(j = i + i; j <= N; j += i)
        isComposite[j] = true

由于对于合数i,其必定能写作i=ab,其中b为某个素数且b<i。因此我们对于每个找到的素数都将以其作为因子的合数打上标记,就可以过滤出所有素数。

总的时间复杂度为O(N(1/2+1/3+1/4+…+1/N))=O(Nlog2N)。

欧拉筛法

尽管普通的筛法已经拥有非常不错的时间复杂度,但是在筛选范围大的情况下依旧是会有点疲软。

我们观察筛法,发现其时间复杂度高的一个根本原因是对于一个合数,其被多次打上了标记,比如12,其可以表示为2*6,也可以表示为3*4,因此其被标记了两次。实际上一个合数被标记的次数为其所有不同素因子的个数。下面我们优化这一过程,保证每个合数仅被标记一次。

prime = []
isComposite = [1,N] filled with false
for(i = 2; i <= N; i++)
    if(!isComposite[i])
        prime.add(i)
    for(j = 0; j < prime.length() && i * prime[j] <= N; j++)
        isComposite[i * prime[j]] = true
        if(i % prime[j] == 0)
            break

下面证明这个算法确实是正确的且每个合数仅被标记一次。

每个合数k都由一个最小素数p,很显然x=k/p是k的最大非平凡因子,而且x的最小素因子不可能小于p。而由于当i=x时,所有小于p的素数均不是x的因子,故在prime[j]小于p时均不会导致循环跳出,故isComposite[x*p]会被执行而导致k被标记为合数。

上面证明了每个合数都被正确标记,下面证明确实仅标记一次。假设当i=y时k被再次标记了,由于p'=k/y>p,而p不是p'的因子,故p一定是y的因子。当prime[j]为p时循环将跳出,故不存在设置isComposite[y*p']的情况。

由于每个合数仅被设置一次,而算法的时间复杂度等同于isComposite被设置的次数,故总的时间复杂度时O(N)。

乘法逆元

$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互质,那么可以利用扩展欧几里得算法,获得公式

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

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

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

一些环上定长位移问题

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

我们能访问的点为$at\mod 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\mod 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)\mod 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的因子中最长反链可以由所有度数正好为$\lfloor \frac{n}{2} \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\mod p$。

由于$a$生成的循环群 的大小一定不会超过$p$,因此我们仅需要考虑$0\leq x\leq p-1$。我们可以利用BSGS算法来计算。记$k=\sqrt{p}$,我们提前计算$a^0,a^1,\ldots,a^k$,并将其存入哈希表中。由于假如$x$存在,那么记$i=\lfloor \frac{x}{k}\rfloor$,$j=x \mod 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\mod p$。

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

最后一项,我们可以用扩欧计算$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\mod p$且$a<p$。

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

由于$g$是原根,因此

很显然上面公式有解,前提条件是$\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\mod p$

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

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

我们上面的公式只能计算$\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}$是区间内的分数,那么有:

因此结论得到证明。

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

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

现在问题变成了处理解决$\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'=\lceil \frac{c'}{d'} \rceil$。

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

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

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

这里我们将约数条件代入,可以得出:

这里我们无需关心$k=\lfloor \frac{xn}{p} \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$的序列中所有数组成的集合,那么结果就是

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

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

莫比乌斯函数的时间复杂度为$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$个数组成集合。

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

到此,算法结束。

提供一道题目

欧拉定理

欧拉定理:若正整数$x$与$m$互质,那么一定有$x^{\varphi(m)}=1\mod m$。其中$\varphi$是欧拉函数。

扩展欧拉定理:对于任意正整数$x$、$m$与某个非负整数$b$,若$b\geq m$,那么一定满足$x^b\mod m=x^{(b\mod \varphi(m))+\varphi(m)}\mod m$

命题1:给定两个互质的数$x$,$p$,记$n$是最小的满足$x^n=1\mod p$的指数,那么若有$x^m=1\mod p$,则一定满足$n\mid m$

证明:

假如$m$不能整除$n$,那么可以推出:

这其实就类似于辗转相除法,我们可以能得出$x^{gcd(m,n)}=1$,考虑到$gcd(m,n)<n$,这与$n$是最小的归1指数相悖,因此假设不成立。

命题2:若$t$是$x$的最小归1指数,那么对于任意$k\mid t$,都至少存在一个正整数$y$,满足$k$是$y$的最小归一整数

证明:

同理:

由于$\frac{tv}{k}\geq t$,因此一定有$v\geq k$,故$k$是$x^{\frac{t}{k}}$的最小归一指数。

问题1:给定$n$个数$a_1,a_2,\ldots,a_n$,要求对于$1\leq i\leq n$,计算$\varphi(a_i)$

这题实际上要求我们计算欧拉函数。下面说几种我知道的计算方式:

我们可以$O(\sqrt{a_i})$时间复杂度内找到$a_i$的所有素因子,之后根据欧拉函数是积性函数的特质直接$O((\log_2a_i)^2)$时间复杂度内算出$\varphi(a_i)$。总的时间复杂度为$n\sqrt{M}$,其中$M=\max(a_1,a_2,\ldots,a_n)$。

上面的方式可以用Pollard Rho算法替代,这样时间复杂度就能优化到$nM^{\frac{1}{4}}\log_2M$。

问题2:给定两个互质的整数$n$和$x$,要求对所有$n$的因子$d$,计算最小的正整数$m_d$,满足$x^{m_d}=1\mod d$,其中$x<n\leq 10^{14}$

很显然我们可以利用欧拉函数计算。

我们先对$n$进行因式分解,算出所有因子和素因子。现在对于某个因子$d$,我们要计算$m_d$。

一种显然的想法就是遍历所有$m_d$的因子,并判断是否可以满足条件。这样的话时间复杂度为$O(D^2)$,其中$D$表示$n$的因子数。这种做法是可以的,因为可以证明$D\leq 20000$。

下面我们来考虑另外一种更有趣的做法。很显然我们可以从任意某个$x$的归1指数除去一些因子得到最小归1指数(命题1),这意味着我们可以遍历所有$d$的素因子,并尝试除去这些素因子,如果除去后仍然是归1因子,我们就真的除去,否则恢复。这是一个贪心过程,可以证明最多发生$P+\log_2 d$次尝试,$P$是$n$以内的数最多拥有的素因子数。

上面方法还剩下一个问题,如何对欧拉函数分解所有质因数呢。欧拉函数的定义为:

这也说明了$n$及其所有因子的欧拉函数的值可能的素因子为:$p_1,p_2,\ldots, p_k$,以及$p_1-1,p_2-1,\ldots, p_k-1$分解出的所有质因子,这样质因子总数仅为$P^2+P$个,是相当有限的。

这里我们还需要证明一下分解$p_1-1,p_2-1,\ldots, p_k-1$需要的时间复杂度。

第一种方式的时间复杂度为$O(\sqrt{n}+D^2)$,第二种方式的时间复杂度为$O(\sqrt{n}+D(P+\log_2 n)$。还是非常快的。

问题3:给定任意两个正整数$a,m$,以及一个非负整数$b$,要求计算$a^b\mod m$。其中$a,m\leq 10^9,b\leq 10^{20000000}$

当$b<m$时,我们可以直接快速幂带走。现在考虑当$b\geq m$时,我们可以先计算出$\varphi(m)$,之后利用扩展欧拉定理对$b$取模即可。

给一道题目

问题4:给定$n$个数$a_1,a_2,\ldots,a_n$,以及$q$个请求,每个请求给定左右边界$l_i,r_i$和数值,要求计算$a_l^{a_{l+1}^{\ldots ^{a_r}}}$

由于指数很大,所以我们势必会用到扩展欧拉定理。但是我们发现指数的性质下无法使用倍增之类的预处理技术。

但是实际上你会发现一个非常重要的性质,我们在处理$a_l^x$时使用的模数是$\varphi(m)$,而在处理$a_{l+1}^x$时使用的模数是$\varphi^2(m)$,之后的同理。

而欧拉函数的定义为$\varphi(x)=x\prod_{i=1}^k(1-\frac{1}{p_i})$。当$x$不是偶数的时候,一定有$\varphi(x)\leq x\cdot \frac{1}{2}$,而当$x$不是偶数的时候,这说明其素因子都是奇数,那么$2\mid p_i - 1 \mid \varphi(x)$,即$\varphi(x)$是偶数,因此有$\varphi^2(x)\leq \varphi(x)\cdot \frac{1}{2}$,总结就是$\varphi^2(x)\leq \frac{x}{2}$。

这意味着我们可以暴力回答每个请求,且每个请求仅前$2\log_2 m$个元素会对结果产生影响,而后面的的所有指数都会被模上$1$,即结果总是$0$。

回答每个请求的时间复杂度为$O(\log_2 m)$,总的时间复杂度还需要加上预处理欧拉函数的时间。

给一道题目

取模运算的一些问题

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

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

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

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

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

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

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

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

记$x_i=x_{i-1}\mod 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 (\lceil\frac{a_i}{d}\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$

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

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

参考资料