狄利克雷卷积高效实现的关键在于利用积性函数性质在线性筛中同步计算质数幂处的卷积值，而非暴力枚举约数；需预处理最小质因子、手动推导 $(f*g)(p^k)$、按积性拼接合数值，并统一数组下标从1开始对应数学定义。
直接说结论：在 C++ 中实现狄利克雷卷积（Dirichlet 卷积）本身不难，但要让它和积性函数配合高效运算，关键不在卷积公式本身，而在**预处理方式、函数存储结构、以及是否利用积性性质跳过重复计算**。硬套定义循环枚举约数，O(n log n) 一跑就超时；真正实用的写法必须依赖积性函数的构造逻辑。
为什么不能直接暴力实现 dirichlet_convolution
常见错误是写成这样：
vector<long long> dirichlet_convolution(const vector<long long>& f, const vector<long long>& g) {
int n = f.size();
vector<long long> h(n);
for (int i = 1; i <p>问题在于：</p>
<ul>
<li>输入 <code>f</code> 和 <code>g</code> 若是积性函数（如 <code>mu</code>、<code>phi</code>、<code>d</code>），它们的值本可通过线性筛 O(n) 得到，但此函数对每个 <code>i</code> 都重新枚举约数，完全抛弃了积性结构</li>
<li>若 <code>f</code>、<code>g</code> 是完全积性函数（如 <code>N(n)=n</code> 或 <code>I(n)=1</code>），卷积结果可能有闭式解（如 <code>id * 1 = sigma_1</code>），没必要算</li>
<li>多数实际场景（如杜教筛、莫比乌斯反演）只需求前缀和 <code>sum_{i=1}^n (f*g)(i)</code>，而非全部点值 —— 暴力卷积反而掩盖了可优化路径</li>
</ul>
<h3>正确做法：用线性筛驱动卷积结果生成</h3>
<p>核心思路：不先求出 <code>f</code> 和 <code>g</code> 全数组再卷，而是在线性筛过程中，**同步计算 <code>(f*g)(p^k)</code>，再按积性拼接合数处的值**。前提是 <code>f</code> 和 <code>g</code> 都是积性函数（这是绝大多数数论题的前提）。</p>
<p>你需要：</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/xiazai/skill5502" title="C++ Code Review Master"><img
src="https://img.php.cn/upload/skill/000/000/081/179051228971575.jpg" alt="C++ Code Review Master" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/xiazai/skill5502" title="C++ Code Review Master" class="overflowclass">C++ Code Review Master</a>
<p class="overflowclass">组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。</p>
</div>
<a rel="nofollow" href="/xiazai/skill5502" title="C++ Code Review Master" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div>
<ul>
<li>一个标准线性筛框架，记录最小质因子 <code>lp[i]</code> 和其幂次 <code>cnt[i]</code>（或用 <code>min_prime_power</code> 数组）</li>
<li>对每个质数幂 <code>p^k</code>，手动推导 <code>(f*g)(p^k) = sum_{i=0}^k f(p^i) * g(p^{k-i})</code> —— 这一步必须手算，无法自动泛化</li>
<li>例如：<code>f = mu</code>, <code>g = 1</code> → <code>(mu*1)(p^k) = [k==0]</code> → 结果就是单位元 <code>epsilon</code>；<code>f = phi</code>, <code>g = 1</code> → <code>(phi*1)(p^k) = p^k</code> → 就是 <code>id</code> 函数</li>
<li>筛到合数 <code>i = p * j</code> 时，若 <code>p ∤ j</code>，直接乘：<code>(f*g)[i] = (f*g)[p] * (f*g)[j]</code>；若 <code>p | j</code>，则需用已存的 <code>p^k</code> 对应值更新</li>
</ul>
<h3>常见积性函数组合的卷积结果要背熟</h3>
<p>实际编码中，90% 的 <code>Dirichlet</code> 卷积调用不是现场算，而是查表替换。以下组合必须条件反射：</p>
<ul>
<li>
<code>mu * 1 == epsilon</code>（即 <code>epsilon[n] = (n==1)</code>）→ 莫比乌斯反演基础</li>
<li>
<code>phi * 1 == id</code>（即 <code>id[n] = n</code>）→ 常用于化简 <code>sum phi(d)</code>
</li>
<li>
<code>mu * id == phi</code> → 注意顺序：<code>(mu * id)(n) = sum_{d|n} mu(d) * (n/d) = phi(n)</code>
</li>
<li>
<code>d * 1 == sigma_0 * 1 == sum_{d|n} d( d )</code>，但更常用的是 <code>d = 1 * 1</code>，所以 <code>d * 1 = 1 * 1 * 1</code>，即三重单位卷积</li>
<li>
<code>sigma_k = id^k * 1</code>，其中 <code>id^k[n] = n^k</code>，这个关系决定了如何筛 <code>sigma_1</code>（约数和）</li>
</ul>
<p>这些不是“理论知识”，是 C++ 实现时的 <strong>分支判断依据</strong>：看到输入是 <code>mu</code> 和 <code>1</code>，直接返回 <code>epsilon</code> 数组，别筛。</p>
<h3>最容易被忽略的坑：函数定义域与数组下标偏移</h3>
<p>所有资料里写的 <code>f(n)</code>，n 从 1 开始；但 C++ 数组从 0 开始。新手常犯的错：</p>
<ul>
<li>把 <code>f[1]</code> 存成 <code>f[0]</code>，导致 <code>dirichlet_convolution</code> 里 <code>i % d == 0</code> 判断错位</li>
<li>筛法中 <code>phi[1] = 1</code>，但忘了初始化 <code>phi[0]</code> 是无定义的，若 vector 大小为 n+1，下标 0 应闲置或设为 0</li>
<li>调用 <code>sum_{i=1}^n (f*g)(i)</code> 时，误写成 <code>accumulate(h.begin(), h.end(), 0LL)</code>，把 <code>h[0]</code>（非法）也加进去了</li>
</ul>
<p>建议统一约定：<code>vector<t> f(n+1)</t></code>，其中 <code>f[i]</code> 对应数学上的 <code>f(i)</code>，<code>i ∈ [1, n]</code>，<code>f[0]</code> 不使用（或 assert 报错）。这点在多人协作或封装模板时特别关键。</p></long></long></long></long>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
