循环不变式
WeLikeStudying · · 题解
简介
- 循环不变式是一种较好的设计算法的方法之一，也是我们开发算法前期必须掌握的方法。
- 它的主要思想是为了达到某个目的，在每次循环同时维护一个性质，在循环结束的时后，达到目标性质。
- 与我们小学，初中，高中接触的常见思想：将问题分为与原问题等价但规模更小的子问题（子问题不重叠的我们称作分治，子问题大量重叠的我们称之为动态规划）不同，在求解问题中，我们的实际在求解一连串的相似但不尽相同的问题。
- 在大学教材中，许多基础算法的严格证明都运用了循环不变式，想必大家早已认识到它的重要性。
- 今天我们以一道典型题目为例子，讲解如何使用循环不变式设计算法。
例题
- 我们来一道例题狄利克雷卷积。
-
$$b_k=\sum_{i|k}a_i$$ -
思路
- 直接的做法复杂度是调和级数的
\Theta(n\ln n) ，显然无法通过本题。 - 但是，仔细看一下，以下是
n=10 的情况： - 即使我是瞎点的也可以看出这里面重复颇多，这为我们的优化提供了启示。
- 还有一个有趣的事情，这一题我们我们有一个现成的范本：埃拉托斯特尼筛法，它以从小到大的顺序逐个给出了每个数的质因子，而且其本身的时间复杂度之前已有讨论，是
\Theta(n\ln\ln n) 的。 - 我们将以该算法为外壳，设计求解该问题的算法。
设计循环不变式
- 设计什么样的循环不变式呢？
- 循环不变式的三个步骤：初始状态，中间状态，结束状态，其中初始状态和结束状态是中间状态的特殊情况。
- 可以看出，基本的要求是：和质因子有关的，结果满足
b_k=\sum_{i|k}a_i 的。 - 我们可能一开始会设计出这样的循环不变式：当处理完
p_i （第i 个质数）时，b_k 所累加的a 数组和的下标i 是所有满足i|k 且i 的唯一因子分解（规定如果是质数唯一因子分解是它本身，1 的唯一因子分解为空）中只包含p_1,p_2,\cdots p_i ，初始状态是b_k=a_1 。 - 这个循环不变式是难以维护的。（想一想，为什么）
- 较好的循环不变式是：当处理完
p_i （第i 个质数）时，b_k 所累加的a 数组和的下标j 是所有满足j|k 且\frac kj 的唯一因子分解中只包含p_1,p_2,\cdots p_i 的，初始状态是b_k=a_k 。
维护循环不变式
- 我们选择这样的循环不变式当然是因为它容易维护。
- 我们约定枚举完
p_i 后的b_k 数组的值为b_k^{(i)} 以便讲解（特别地b_k^{(0)}=a_k ）。 - 考虑在枚举
p_i 的时候，我们让b_k 的值由b_k^{(i-1)} 变为b_k^{(i)} 。 - 考虑
b_k^{(i)}-b_k^{(i-1)} ，可以发现它是：当处理完p_i （第i 个质数）时，b_k 所累加的a 数组和的下标j 是所有满足j|k 且\frac kj 的唯一因子分解中只包含p_1,p_2,\cdots p_{(i-1)} 且一定有p_i 的，也就是\frac k{j\cdot p_i} 的唯一因子分解中只包含p_1,p_2,\cdots p_i 的，即b_{k/p_i}^{(i)} 。 - 可以发现我们如果按顺序执行埃氏筛法就可以保证
b_{k/p_i}=b_{k/p_i}^{(i)} 。（想一想，为什么） - 于是整个算法也可以确定下来了：时间复杂度
\Theta(n\ln\ln n) ，空间复杂度\Theta(n) ，可以通过例题。
代码实现
#include<fstream>
#define uint unsigned int
const uint MAXN=2e7+1;
using namespace std;
uint n,seed,b[MAXN],ans=0;
bool np[MAXN];
inline uint getnext(){
seed^=seed<<13;
seed^=seed>>17;
seed^=seed<<5;
return seed;
}
int main()
{
scanf("%u%u",&n,&seed);
for(int i=1;i<=n;++i)b[i]=getnext();
np[1]=1;
for(int i=1;i<=n;++i)
{
if(!np[i])
for(int j=1;i*j<=n;++j)
b[i*j]+=b[j],np[i*j]=1;
ans^=b[i];
}
printf("%u",ans);
return 0;
}总结
- 循环不变式的确是一种巧妙的办法，我们在实际解决问题的时候，要从多角度思考，灵活解决问题。
课后习题
- 思考：如果
b_k 的推导分别是以下的两个式子，我们之前设计的算法还可行吗？b_k=\sum_{i=1}^na_{\lfloor\frac ki\rfloor} b_k=a_k+\sum_{d|k,d\ne k}b_d
习题答案
感谢 @kintsgi 的提醒，我已经将两道习题变成了可以评测的形式，大家如果有兴趣可以去提交。
- 课后习题 1
- 课后习题 2
如果你不会做，我可以提供提示，往下看吧。
提示
目标复杂度都是