0. 一些前置知识
- 莫比乌斯函数：定义 \(\mu(x)\) 为：当 \(x\) 含平方因子，则 \(\mu(x) = 0\)；否则设其有 \(p\) 个质因子，\(\mu(x)=(-1)^p\)。
特别的，\(\mu(1)=1\)。
- 莫比乌斯函数的性质：\(\sum \limits_{d | x} \mu(x) = \varepsilon(x)\)
- 欧拉函数更牛逼的性质：\(\sum \limits_{d | x} \varphi(x) = x\)
1. 狄利克雷卷积
1.1 性质
定义两个数论函数的卷积为 \(f * g\)。
性质 1：\(f * g = g * f\)；\(( f * g ) * h = f * (g * h)\)；\((f+g)*h = f*h + g*h\)。
性质 2: \(\varepsilon * f = f\) （由此可以知道 \(\varepsilon\) 为单位元，然后可以定义函数的逆 \(f * f^{-1} = \varepsilon\)。
性质 3：若 \(f(1) \ne 0\)，则 \(f\) 存在逆元。
这个在多项式里面也有提到，就是说可以通过递推构造的形式产生 \(f^{-1}\)。上述命题显然。
性质 4：
有两个积性函数 \(f,g\)。
那么 \(f * g\) 为积性函数，\(f^{-1}\) 为积性函数。
1.2 狄利克雷前缀和
我们要求的是 \(f * 1\)。
根据 SOSDP 的思想，可以枚举每一个质数，进行 SOSDP。时间复杂度 \(O(n \ln \ln n)\)。
例题 1：P5495 Dirichlet 前缀和
模板题，代码如下。
#define uint unsigned int
uint seed;
inline uint getnext(){
seed^=seed<<13;
seed^=seed>>17;
seed^=seed<<5;
return seed;
}
bool vis[20000005];
ll cnt, prim[20000005];
void init(){
for(ll i=2;i<=2e7;i++){
if(!vis[i]) prim[++cnt]=i;
for(ll j=1;j<=cnt && i*prim[j]<=2e7;j++){
vis[i*prim[j]]=1;
if(i%prim[j]==0) continue;
}
}
}
ll n,a[20000005];
void solve(){
n=read(); seed=read();
for(ll i=1;i<=n;i++)
a[i]=getnext();
for(ll i=1;i<=cnt;i++){
for(ll j=1;j<=n/prim[i];j++){
a[j*prim[i]]+=a[j];
}
}
ll ans=0;
for(ll i=1;i<=n;i++) ans^=a[i];
cout<<ans<<endl;
return;
}