题解：CF439E Devu and Birthday Celebration

belot · 2025-02-26 20:59:42 · 题解

Devu and Birthday Celebration

设 d=\gcd(a_1, a_2, \dots, a_f)，则题目要求的是 d 为 1 时 \sum_{i=1}^fa_i=n 的答案。而对于 \sum_{i=1}^fa_i=n 这个问题的答案记为 g(f, n)。则用插板法可以容易地求出 g(f, n)=(^{n-1}_{f-1})，则接下来的问题就是消去 d\not=1 时的答案。首先显然有 d|n，且这个问题应当是使用容斥解决，而对于有关 \gcd=1 的容斥，可以使用莫比乌斯反演。莫比乌斯反演的结论是若有 f(n)=\sum_{d|n}g(d)，则 g(n)=\sum_{d|n}f(d)\times\mu(\frac nd) 。此题中，设整道题的答案为 h(f, n)，则有 g(f, n)=\sum_{d|n}h(f, \frac nd)，其中 h(f, \frac nd) 的意义为长度为 f 的数列 \gcd=d 时的答案。此时使用莫比乌斯反演，就有 h(f, n)=\sum_{d|n}g(f, d)\times\mu(\frac nd)。

使用线性筛筛出 \mu，每个询问直接 O(\sqrt n) 卷积即可。时间复杂度 O(q\sqrt n)。

Code 在此。