求\(b_k=\sum\limits_{i|k}{a_i}\)
考虑\(i=p_1^k,j=p_1^{k+1}\)，若我们已经求出了\(b_i\)，则易知\(b_j=b_i+a_j\)
然后根据上面的方法，考虑对于所有的\(k=p_1^{k1}p_2^{k2}...p_l^{kl}\)，若\(j=p_2^{k2}...p_l^{kl}\)，我们已经求出所有的\(c_k=a_j+a_{p1\times j}+a_{p1^2\times j}+...+a_{p1^{k1}\times j}\)
则对于\(i=p_1^{k1},j=p_1^{k1}p_2\)，若我们求出了\(c_i,c_j\)，则\(b_j=c_i+c_j\)
进一步的，对于\(i=p_1^{k1}p_2,j=p_1^{k1}p_2^2\)，若我们求出了\(b_i\)，则\(b_j=b_i+c_j\)
再进一步，对于\(i=p_1^{k1}p_2^{k2},j=p_1^{k1}p_2^{k2+1}\)，若我们求出了\(b_i\)，则\(b_j=b_i+c_j=\sum\limits_{t=0}^{k2+1}c_{p_1^{k1}p_2^t}\)
我们发现，若我们重复上述步骤，则对于任意数\(k=p_1^{k1}p_2^{k2}...p_l^{kl}\)，我们都可以求出\(b_k\)
那么如何快速求出\(c_i\)呢？
我们可以先令\(c_i=a_i\)
当我们枚举出一个质数\(p_i\)时，我们可以枚举\(j=1\)~\(n\)，然后令\(c_{j\times p_i}+=c_j\)即可
然后我们又发现，不需要这么多个数组，只需要一个数组滚动更新即可
上代码：
#include<bits/stdc++.h>
#define ll unsigned int
using namespace std;
const ll N=2e7+15;
ll n,seed;
ll b[N],ans;
bool np[N];
ll getnext()
{
seed^=seed<<13;
seed^=seed>>17;
seed^=seed<<5;
return seed;
}
int main()
{
scanf("%u %u",&n,&seed);
for(ll i=1;i<=n;i++) b[i]=getnext();
np[1]=1;
for(ll i=1;i<=n;i++)
{
if(!np[i])
for(ll j=1;i*j<=n;j++)
b[i*j]+=b[j],np[i*j]=1;
ans^=b[i];
}
printf("%u\n",ans);
return 0;
}