题目
题目链接:https://www.luogu.com.cn/problem/P5495
给定一个长度为 (n) 的数列 (a_1,a_2,a_3,dots,a_n)。
现在你要求出一个长度为 (n) 的数列 (b_1,b_2,b_3,dots,b_n),满足
[b_k=sum_{i|k}a_i
]
由于某些神秘原因,这里的 (b_k) 要对 (2^{32}) 取模。
(nleq 2 imes 10^7)。
思路
如果 (x=prod_{p_iin ext{prime}}p_i^{a_i}),(y=prod_{p_iin ext{prime}}p_i^{b_i}),那么 (x) 可以贡献到 (y) 当且仅当 (forall i,a_ileq b_i)。
那么直接枚举质数,用类似埃氏筛的方法即可。
时间复杂度 (O(nlog log n))。
代码
#include <bits/stdc++.h>
#define int unsigned int
using namespace std;
const int N=20000010;
int n,m,seed,a[N],prm[N];
bool v[N];
inline int getnext(){
seed^=seed<<13;
seed^=seed>>17;
seed^=seed<<5;
return seed;
}
signed main()
{
cin>>n>>seed;
for (int i=1;i<=n;i++) a[i]=getnext();
for (int i=2;i<=n;i++)
if (!v[i])
{
prm[++m]=i;
for (int j=i*2;j<=n;j+=i) v[j]=1;
}
for (int i=1;i<=m;i++)
for (int j=1;j*prm[i]<=n;j++)
a[j*prm[i]]+=a[j];
for (int i=2;i<=n;i++) a[1]^=a[i];
cout<<a[1];
return 0;
}