循环不变式

· · 题解

简介

例题

思路

设计循环不变式

维护循环不变式

代码实现

#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;
}

总结

课后习题

习题答案

感谢 @kintsgi 的提醒,我已经将两道习题变成了可以评测的形式,大家如果有兴趣可以去提交。

如果你不会做,我可以提供提示,往下看吧。

提示

目标复杂度都是 O(n\log\log n),第一题差分,第二题倍增,这两题并不难,一般提示到这里就会做了。