Dirichlet 前缀及后缀和 Divan and Kostomuksha

Dirichlet前缀和

概述

狄利克雷前缀和是用来求解这样的问题，给定 { a n } \{a_n\} { an?}，求解 { b n } \{b_n\} { bn?}，使得$$b_k=\sum _{d|k}{a}_d$$

代码

例题处分析

for(int i=1;i<=CntPrime;i++)for(int j=1;j*Prime[i]<=N;j++)B[ j*Prime[i] ]+=B[j];

例题

https://www.luogu.com.cn/problem/P5495
给一个数列$a$，长度在$2\times 10^7$以内，让你求一个数列$b$满足
$$b_k=\sum _{i|k}{a}_i$$

• 因为是根据$a$推$b$，我们可以直接枚举$i$，设它的倍数为$j$，那么有$$b[j]=b[j]+a[i]$$这样得到的$b$就是要求的数列，这样的时间复杂度是$O(nlnn)$的，因为调和级数趋近于$lnn+C$
• 由于范围过大，$O(nlogn)$的时间复杂度会被卡，需要再压缩时间，这其实和欧拉筛是一个道理，我们发现，如果采用这种方法比如说$b_8=a_1+a_2+a_4+a_8$，需要全加上，这里面有很多重复计算，因为$b_4=a_1+a_2+a_4$，所以其实$b_8=b_4+a_8$，其他一个道理，所以我们使用质数作为因子进行加速，可以把时间复杂度降到$O(nloglogn)$

上面模板题

#include <bits/stdc++.h>using namespace std;typedef long long ll;
const int MAXN = 2e7;
int p[MAXN + 100];
bool vis[MAXN + 100];
int Prime(){
    int tot = 0;for(int i=2;i<=MAXN;i++){
    if(!vis[i]) p[tot++] = i;for(int j=0;j<tot&&p[j]*i<=MAXN;j++){
    vis[i * p[j]] = 1;if(i % p[j] == 0) break;}}return tot;
}
#define uint unsigned int
uint seed;
inline uint getnext(){
    seed^=seed<<13;seed^=seed>>17;seed^=seed<<5;return seed;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);int tt = Prime();int n;cin >> n >> seed;vector<uint> a(n + 1);for(int i=1;i<=n;i++) a[i] = getnext();for(int i=0;i<tt;i++){
    for(int j=1;p[i]*j<=n;j++){
    a[p[i]*j] += a[j];}}uint ans = 0;for(int i=1;i<=n;i++){
    ans ^= a[i];}cout << ans;return 0;
}

Dirichlet后缀和

概述

给定 { a n } \{a_n\} { an?}，求 { b n } \{b_n\} { bn?}，使得$$b_k=\sum _{k|d}{a}_d$$

代码

for(int i=1;i<=CntPrime;i++)for(int j=N/Prime[i];j>=1;j--)B[j]+=B[ j*Prime[i] ];

例题

https://codeforces.com/contest/1614/problem/D1
https://codeforces.com/contest/1614/problem/D2
题意就是给出 { a n } \{a_n\} { an?}，让你构造一个数组 { b n } \{b_n\} { bn?}，使得其满足前缀$GCD$的和最大，求这个最大的和

• easy版本数据范围是2e6，hard版本数据范围是2e7，就是用不用素数优化的关系
• 用数组$cnt[i]$表示原数组中是$i$的倍数的数的个数，那么求这个数组显然应该是狄利克雷后缀和，可以仔细想一下，然后打印结果看看
• 考虑dp，设$dp[i]$表示最后一个元素被$i$整除的最大值，设$j$表示$i$的倍数，由$i$推$j$，有$$dp[j]=max(dp[j],dp[i]+cnt[j]\times (j?i))$$其中$j?i$表示$j$相对于$i$的增量

#include <bits/stdc++.h>using namespace std;const int MAXN = 5e6;
long long cnt[MAXN + 100]; 
long long dp[MAXN + 100];
int main(){
    ios::sync_with_stdio(false);cin.tie(0);int n;cin >> n;for(int i=0;i<n;i++){
    int x;cin >> x;cnt[x] += 1;}for(int i=1;i<=MAXN;i++){
    for(int j=i+i;j<=MAXN;j+=i){
    cnt[i] += cnt[j];}}dp[1] = cnt[1];long long ans = 0;for(int i=1;i<=MAXN;i++){
    for(int j=i+i;j<=MAXN;j+=i){
    dp[j] = max(dp[j], 1ll * cnt[j] * (j - i) + dp[i]);}ans = max(ans, dp[i]);// cout << dp[i] << '\n';}cout << ans;return 0;
}

用质数优化

#include <bits/stdc++.h>using namespace std;typedef long long ll;
const int MAXN = 2e7;
int p[MAXN + 100];
bool vis[MAXN + 100];
int cnt[MAXN + 100];
ll dp[MAXN + 100];
int Prime(){
    int tot = 1;for(int i=2;i<=MAXN;i++){
    if(!vis[i]) p[tot++] = i;for(int j=1;j<tot&&p[j]*i<=MAXN;j++){
    vis[i * p[j]] = 1;if(i % p[j] == 0) break;}}return tot;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);int n;int tt = Prime();cin >> n;for(int i=0;i<n;i++){
    int x;cin >> x;cnt[x] += 1;}for(int i=1;i<tt;i++){
    for(int j=MAXN/p[i];j>=1;j--){
    cnt[j] += cnt[j * p[i]];}}dp[1] = cnt[1];long long ans = 0;for(int i=1;i<=MAXN;i++){
    for(int j=1;i*p[j]<=MAXN;j++){
    int k = p[j] * i;dp[k] = max(dp[k], 1ll * cnt[k] * (k - i) + dp[i]);}ans = max(ans, dp[i]);// cout << dp[i] << '\n';}cout << ans;return 0;
}

未完待续

• 这似乎和莫比乌斯反演有点关系，留个坑