路终会有尽头，但视野总能看到更远的地方。

祝贺博客文章数量突破500！
然而这并没有什么卵用。

其实这是有卵用的。
只是同机房的同学选择用笔记本记录自己的OI之路，而我选择用博客的方式而已。
至于为什么？
因为电子的Latex更爽吧。。。
而且，在我退役后也能帮助到更多的人。

题目大意

    没有得到激光武器的苏联十分生气，他们决定派遣一支特种部队强行登陆美国并造成一定的袭击。Reddington得到的情报是他们将在佛罗里达海岸登陆，他决定派遣他的手下去阻击他们。可惜的是，Reddington由于不听从总统的意见，手中的部队只剩下了$N$个人。人与人之间会有一定的矛盾值，第$i$个人与第$j$个人的矛盾值为$T_{i,j}$，并且有$T_{i,i}=0$，$T_{i,j}=T_{j,i}$。
    Reddington希望将这$N$个人分为两支小分队，记为$A,B$，每个人要么属于分队$A$要么属于分队$B$。对于一支小分队$S$，其内部的不安值

$$D(S)=\max_{u\in S,v\in S}T_{u,v}$$

    显然的，假如一支分队的不安值很高，那么作战能力就会很差。现在给定你$N$以及一个$N\times N$的矩阵$T$，你需要告诉Reddington，最小的$D(A)+D(B)$是多少。

题目大意

    大战将至, 美国决定实行计划经济。美国西部总共有$N$个城市，编号为$0\rightarrow N−1$，以及$M$条道路，道路是单向的。其中城市$0$是一个大城市，里面住着$K$个人，而城市$N−1$是一个农业城市。现在所有城市$0$的居民都需要到城市$N−1$去领取食物。由于担心体力不支，所以居民都会采取开车的形式出行。但道路不是无限宽的，对于一条道路，会有$c_i$的限制，表示在同一天内，最多只能有$c_i$辆车同时在这条道路上行驶。一条道路的长度为$1$，每辆车的行驶速度也可以假定为$1$每天。城市$N−1$会在每个居民都到达后马上开始发放食物。现在Reddington想知道，假如在最优安排下，居民最早能在多少天后领到食物。假如没有居民那就不需要发放食物，默认为第$0$天。

题目大意

    Reddington是美国的海军上将。由于战争局势十分紧张，因此他需要时刻关注着苏联的各个活动，避免使自己的国家陷入困境。苏联在全球拥有$N$个军工厂，但由于规划不当，一开始这些军工厂之间是不存在铁路的，为了使武器制造更快，苏联决定修建若干条道路使得某些军工厂联通。
    Reddington得到了苏联的修建日程表，并且他需要时刻关注着某两个军工厂是否联通，以及最早在修建哪条道路时会联通。具体而言，现在总共有$M$个操作，操作分为两类：
    •$0\,\,u\,\,v$，这次操作苏联会修建一条连接$u$号军工厂及$v$号军工厂的铁路，注意铁路都是双向的;
    •$1\,\,u\,\,v$，Reddington需要知道$u$号军工厂及$v$号军工厂最早在加入第几条条铁路后会联通，假如到这次操作都没有联通，则输出$0$;
    作为美国最强科学家，Reddington需要你帮忙设计一个程序，能满足他的要求。

题目大意

    求：

$$g(a,b,c,l,r)=\sum_{i=l}^ri\lfloor\frac{ai+b}c\rfloor$$

题目大意

    小Y是一个喜欢玩游戏的OIer。一天，她正在玩一款游戏，要打一个Boss。
    虽然这个Boss有$10^{100}$点生命值，但它只带了一个随从——一个只有$m$点生命值的“恐怖的奴隶主”。
    这个“恐怖的奴隶主”有一个特殊的技能：每当它被扣减生命值但没有死亡（死亡即生命值$\leq0$），且Boss的随从数量小于上限$k$，便会召唤一个新的具有$m$点生命值的“恐怖的奴隶主”。
    现在小Y可以进行$n$次攻击，每次攻击时，会从Boss以及Boss的所有随从中的等概率随机选择一个，并扣减$1$点生命值，她想知道进行$n$次攻击后扣减Boss的生命值点数的期望。为了避免精度误差，你的答案需要对$998244353$取模。

题目大意

    小Y是一个爱好旅行的OIer。一天，她来到了一个新的城市。由于不熟悉那里的交通系统，她选择了坐地铁。
    她发现每条地铁线路可以看成平面上的一条曲线，不同线路的交点处一定会设有换乘站。通过调查得知，没有线路是环线，也没有线路与自身相交。任意两条不同的线路只会在若干个点上相交，没有重合的部分，且没有三线共点的情况。即，如图所示的情况都是不存在的：

小Y坐着地铁$0$号线，路上依次经过了$n$个换乘站。她记下了每个换乘站可以换乘的线路编号，发现每条线路与她所乘坐的线路最多只有$2$个换乘站。现在小Y想知道，除掉她经过的换乘站以外，这个城市里最少有几个换乘站。只有你告诉她正确的答案，她才会答应下次带你去玩呢。

数论函数

定义域为正整数的函数，值域为复数的函数。

积性函数

规定$f(1)=1$，当$(a,b)=1$时满足$f(ab)=f(a)f(b)$的函数。

完全积性函数

完全积性函数是积性函数。
满足$\forall a,b$，$f(ab)=f(a)f(b)$。

常见的积性函数

狄利克雷卷积

定义两个数论函数$f,g$的狄利克雷卷积为：

性质

交换律：$f*g=g*f$
结合律：$(f*g)*h=f*(g*h)$
分配率：$f*(g+h)=f*g+f*h$
单位元：$f*e=e*f=f$（$e$是单位函数）

常见的狄利克雷卷积

积性函数的性质

若$f(x),g(x)$均为积性函数，则：

$h(x)=f(x^p)$为积性函数。
$h(x)=f^p(x)$为积性函数。
相乘$h(x)=f(x)g(x)$为积性函数。
狄利克雷卷积$h(x)=\sum\limits_{d\mid x}f(d)g(\frac xd)$为积性函数。

线性筛

线性筛可以在严格线性的时间内求出积性函数$f(1\rightarrow n)$的值。

要求

$f$是一个积性函数。

线性筛的思想

使用最小的$p_1$去筛掉其他的数。

将$n$分为三类考虑。

1. $n$是质数，根据定义得到$f(i)$的值。
2. $\frac n{p_1}\bmod p_1=0$，说明$\frac n{p_1}$与$n$的质因子集相同，考虑其变化。
3. $\frac n{p_1}\bmod p_1\neq0$，说明$\frac n{p_1}$与$p_1$互素，利用积性函数的性质得到$f(n)=f(\frac n{p_1})f(p_1)$。

素数线性筛

保证每个合数被其最小的素数筛掉，因此时间复杂度是线性的。
当满足$i\bmod p[j]=0$时，说明$p[j]$整除$i$，那么$p[j]$必然整除$i\cdot p[j+1]$，因此无需继续筛。

1
2
3
4
5
6
7
8
9
10
11

int vst[maxn],Prime[maxn],cnt=0; //prime

void Prime_Sieve(int n) {
	for(int i=2; i<=n; i++) {
		if(!vst[i])Prime[++cnt]=i;
		for(int j=1; j<=cnt&&i*Prime[j]<=n; j++) {
			vst[i*Prime[j]]=1;
			if(i%Prime[j]==0)break;
		}
	}
}

欧拉函数

欧拉函数$\varphi(n)$定义为在$n$以内与$n$互质的正整数个数。

欧拉函数的性质

若$n=p^k$，其中$p$是素数，$\varphi(n)=p^k-p^{k-1}$。

证明：
小于$p^k$的正整数有$p^k-1$个，其中和$p^k$不互质的正整数为$\lbrace p,2p,\ldots,(p^{k-1}-1)p\rbrace$，共$p^{k-1}-1$个数，因此$\varphi(n)=p^k-p^{k-1}$。

若$(p,q)=1$，则$\varphi(pq)=\varphi(p)\varphi(q)$。

证明：
根据上述，$\varphi$是积性函数，因此显然。

设$n=\prod_{i=1}^kp_i^{a_i}$，其中$p_i$是素数，$\varphi(n)=n\prod_{i=1}^k(1-\frac 1{p_i})$。

证明：
由上述两式显然。

欧拉函数线性筛

设$p_1$是$n$的最小质因子，$n’=\frac{n}{p_1}$，在线性筛中，$n$通过$n’\times p_1$被筛掉。

• 当$n’\bmod p_1=0$，即$a_1\gt1$时，$n’$含有$n$的所有质因子，则有： $$\begin{aligned} \varphi(n)&=n\prod_{i=1}^k\frac{p_i-1}{p_i} \\ &=p_1\times n'\prod_{i=1}^k\frac{p_i-1}{p_i} \\ &=p_1\times\varphi(n') \end{aligned}$$
• 当$n’\bmod p_1\neq0$，即$a_1=1$时，$n’$与$p_1$互素，而欧拉函数是积性函数，故： $$\begin{aligned} \varphi(n)&=\varphi(p_1)\times\varphi(n') \\ &=(p_1-1)\varphi(n') \end{aligned}$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

const int maxn=1000005;

int vst[maxn],Prime[maxn],cnt=0; //prime
int Phi[maxn]; //phi

void Phi_Table(int n) {
	Phi[1]=1;
	for(int i=2; i<=n; i++) {
		if(!vst[i]) {
			Prime[++cnt]=i;
			Phi[i]=i-1;
		}
		for(int j=1; j<=cnt&&i*Prime[j]<=n; j++) {
			vst[i*Prime[j]]=1;
			if(i%Prime[j]==0) {
				Phi[i*Prime[j]]=Phi[i]*Prime[j];
				break;
			}
			Phi[i*Prime[j]]=Phi[i]*Phi[Prime[j]];
		}
	}
}

莫比乌斯函数

设$n=\prod_{i=1}^kp_i^{a_i}$

莫比乌斯函数线性筛

当$n$为素数时，根据定义有$\mu(n)=-1$。

设$p_1$是$n$的最小质因子，$n’=\frac{n}{p_1}$，在线性筛中，$n$通过$n’\times p_1$被筛掉。

• 当$n’\bmod p_1=0$，即$a_1\gt1$时，由定义可知： $$\mu(n)=0$$
• 当$n’\bmod p_1\neq0$，即$a_1=1$时，$n’$与$p_1$互素，而欧拉函数是积性函数，故：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

const int maxn=1000005;

int vst[maxn],Prime[maxn],cnt=0; //prime
int Mobius[maxn]; //mobius

void Mobius_Table(int n) {
	Mobius[1]=1;
	for(int i=2; i<=n; i++) {
		if(!vst[i]) {
			Prime[++cnt]=i;
			Mobius[i]=-1;
		}
		for(int j=1; j<=cnt&&i*Prime[j]<=n; j++) {
			vst[i*Prime[j]]=1;
			if(i%Prime[j]==0) {
				Mobius[i*Prime[j]]=0;
				break;
			}
			Mobius[i*Prime[j]]=-Mobius[i];
		}
	}
}

约数个数函数

约数个数函数$d(n)$定义为$n$的约数个数。

约数个数公式

若$n=\prod_{i=1}^kp_i^{a_i}$，则：

约数个数线性筛

当$n$为素数时，根据定义有$d(n)=2$。

设$p_1$是$n$的最小质因子，$n’=\frac{n}{p_1}$，在线性筛中，$n$通过$n’\times p_1$被筛掉。

• 当$n’\bmod p_1=0$，即$a_1\gt1$时，设$last$为$n’$中$p_1$的指数，由约数个数公式可知： $$d(n)=d(n')\times\frac{last+2}{last+1}$$
• 当$n’\bmod p_1\neq0$，即$a_1=1$时，$n’$与$p_1$互素，而约数个数函数是积性函数，故： $$\begin{aligned} d(n)&=d(p_1)\times d(n') \\ &=2d(n') \end{aligned}$$

在实现时，使用Min_Divnum[i]来记录$n’=i$时的$last$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

const int maxn=1000005;

int vst[maxn],Prime[maxn],cnt=0; //prime
int d[maxn],Min_Divnum[maxn]; //divisors

void Divisors_Number_Table(int n) {
	for(int i=2; i<=n; i++) {
		if(!vst[i]) {
			Prime[++cnt]=i;
			Min_Divnum[i]=1;
			d[i]=2;
		}
		for(int j=1; j<=cnt&&i*Prime[j]<=n; j++) {
			vst[i*Prime[j]]=1;
			if(i%Prime[j]==0) {
				Min_Divnum[i*Prime[j]]=Min_Divnum[i]+1;
				d[i*Prime[j]]=d[i]/(Min_Divnum[i]+1)*(Min_Divnum[i]+2);
				break;
			}
			Min_Divnum[i*Prime[j]]=1;
			d[i*Prime[j]]=d[i]*d[Prime[j]];
		}
	}
}

约数和函数

约数个数函数$\sigma(n)$定义为$n$的约数个数。

约数和公式

若$n=\prod_{i=1}^kp_i^{a_i}$，则：

约数个数线性筛

当$n$为素数时，根据定义有$\sigma(n)=n+1$。

设$p_1$是$n$的最小质因子，$n’=\frac{n}{p_1}$，在线性筛中，$n$通过$n’\times p_1$被筛掉。

• 当$n’\bmod p_1=0$，即$a_1\gt1$时，设$last=p_1^{a_1-1}$也就是$n’$中$p_1$为底的最后一个幂，设$sum=\sum\limits_{i=0}^{a_1-1}p_1^i$，由约数个数公式可知： $$\sigma(n)=\sigma(n')\times\frac{sum+last}{sum}$$
• 当$n’\bmod p_1\neq0$，即$a_1=1$时，$n’$与$p_1$互素，而约数个数函数是积性函数，故： $$\begin{aligned} \sigma(n)&=\sigma(p_1)\times \sigma(n') \\ &=(p_1+1)\sigma(n') \end{aligned}$$

在实现时，使用Min_Fac_last[i]和Min_Fac_sum[i]来记录$n’=i$时的$last$和$sum$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

typedef long long LL;

const int maxn=1000005;

int vst[maxn],Prime[maxn],cnt=0; //prime
LL f[maxn],Min_Fac_last[maxn],Min_Fac_sum[maxn]; //divisors

void Divisors_Sum_Table(int n) {
	f[1]=1;
	for(int i=2; i<=n; i++) {
		if(!vst[i]) {
			Prime[++cnt]=i;
			Min_Fac_last[i]=i;
			f[i]=Min_Fac_sum[i]=i+1;
		}
		for(int j=1; j<=cnt&&i*Prime[j]<=n; j++) {
			vst[i*Prime[j]]=1;
			if(i%Prime[j]==0) {
				Min_Fac_last[i*Prime[j]]=Min_Fac_last[i]*Prime[j];
				Min_Fac_sum[i*Prime[j]]=Min_Fac_sum[i]+Min_Fac_last[i*Prime[j]];
				f[i*Prime[j]]=f[i]/Min_Fac_sum[i]*Min_Fac_sum[i*Prime[j]];
				break;
			}
			f[i*Prime[j]]=f[i]*(Prime[j]+1);
			Min_Fac_last[i*Prime[j]]=Prime[j];
			Min_Fac_sum[i*Prime[j]]=Prime[j]+1;
		}
	}
}

杜教筛

杜教筛是一种可以在$O(n^\frac23)$的时间内求出特定的积性函数前缀和的方法。
即求出：

要求

能够找到另一个积性函数$g$，使得$(f*g)(x)$的前缀和与$g(x)$的前缀和都很好计算。

主过程

考虑$(f*g)(x)$的前缀和。

因此：

即：

因此若$(f*g)(x)$的前缀和与$g(x)$的前缀和都很好计算，那么可以通过递归，在$O(n^\frac34)$的时间内求出$f$的前缀和。
进一步，若能够通过线性筛预处理$f$在$n^\frac23$内的前缀和，时间复杂度降低到$O(n^\frac23)$。

更具体的，这里分别有欧拉函数与莫比乌斯函数杜教筛的推导。

洲阁筛

杜教筛在时间上虽然很快，但因为其限制条件，并不是所有积性函数都可以使用杜教筛。
洲阁筛可以在$O(\frac{n^\frac34}{\ln n})$的时间内求出大多数积性函数的前缀和。

要求

$f$是一个积性函数。
当$p$是质数时，$f(p^c)$是一个关于$p$的低阶多项式。

洲阁筛的思想

利用$\sqrt n$以外只有$1$个素因子的性质，对素因子进行分类。
再利用除法向下取整只有$\sqrt n$个取值的性质，降低时间复杂度。

主过程

将$[1,n]$中所有数按照是否有$\gt\sqrt n$的质因子分为两类，显然有：

第一部分

这一部分可以直接线性筛解决。

第二部分

对于每个$1\le i\le\sqrt n$，计算

将$\sqrt n$以内的素数从小到大排列为$p_1,p_2,\ldots,p_m$。
设$g_k(i,j)$表示$[1,j]$中与前$i$个素数互质的数的$k$次幂和。
这里的$k$无特别含义，仅仅用来表示其可以写作低阶多项式形式。
初值为$g(0,j)=\sum_{t=1}^jt^k$，那么我们需要的值即为$g_k(m,j)$（与前面所有素数互质，必然是$\sqrt n$后的素数），若能$O(1)$得到$g_k(m,j)$的值，考虑原式前半部分：

可用$O(\sqrt n)$的时间枚举$i$，然后$O(1)$得到第二部分。

考虑转移：

对于一个素数，合法的$j$总数只有$O(\sqrt n)$个，因此粗略计算时间复杂度为：

需要优化。

注意到当$p_{i+1}\gt j$时，$p_{1\cdots i}$已经可以组成所有数，因此此时未被筛掉的仅有$1$，即$g_k(i,j)=1$。
代入下一层递推可以发现：当$p_i\gt\lfloor\frac j{p_i}\rfloor$，即$p_i^2\gt j$时，$g_k(i,j)$的转移变为：

从小到大枚举$i$，一旦发现对于某个$j$有$p_{i_0}^2>j$便可以不再转移，之后若需要用到其在$i_1$时的值，直接用$g_k(i_0,j)-\sum\limits_{i=i_0}^{i_1-1}p_i^k$即可。

用积分可以将时间复杂度近似为$O(\frac{n^\frac34}{\log n})$

第三部分

同样考虑递推，为了剪枝从大的质数往小的递推。

将$\sqrt n$以内的素数从小到大排列为$p_1,p_2,\ldots,p_m$。
设$h(i,j)$表示$[1,j]$中只有$p_{i\cdots m}$质因子的数的$f(x)$求和。

那么初值为$h(m+1,j)=1$，要求$h(0,j)$。
转移方程为：

发现$j$的取值仍只有$O(\sqrt n)$个，因此暴力计算，时间复杂度仍然为

注意到当$p_i\gt j$时，能用这些质因子组成的数只有$1$。
因此有$h(i,j)=1$。

类似地，当$p_i^2\gt j$时，转移变为：

从大到小枚举$i$，如果对于某个$j$有$p_i^2\gt j$，可以不转移，每次用的时候加入$[p_i,\min(j,\sqrt n)]$的质数的$f(p)$即可。

时间复杂度仍然为$O(\frac{n^\frac34}{\ln n})$。

嘴上AC还是不难的，现在我还没有用洲阁筛写一道题。

参考资料

• 线性筛法 - Menci
• 初等数论.pdf - h10
• [51nod1239]欧拉函数之和 - alan_cty
• 论逗逼的自我修养之寒假颓废记 - jiry_2
• 洲阁筛学习 - __debug
• 洲阁筛学习总结 - Semiwaker

题目大意

    小G是一个商人，他有一个电话本。电话本上记下了许多联系人，如timesqr、orzyhb等等。不过Tony对其中的某个联系人的名字$S$特别感兴趣，他从中提取出了这个联系人的名字中的所有片段，如提取出orz的o,r,z,or,rz,orz等等。现在他想请你统计有多少个长度为$k$的片段对$(P[1],P[2],P[3],…,P[k])$，使得在该片段对中所有片段在$S$中出现次数之和为他的幸运数$m$？注意两个片段对不同当且仅当两个片段对的某一位的片段不同，两个片段不同当且仅当这两个片段在$S$中的位置不同。

题目大意（「SDOI2015」约数个数和）

    设$d(x)$为$x$的约数个数，给定$n,m$，求:

$$\sum_{i=1}^n\sum_{j=1}^md(ij)$$

    $n,m\le50000$，多组数据$t\le50000$

题目大意（「bzoj4176」Lucas的数论）

    设$d(x)$为$x$的约数个数，给定$n$，求:

$$\sum_{i=1}^n\sum_{j=1}^nd(ij)$$

    $n\le10^9$