2018 CCPC网络赛1002 HDU6439 Congruence equation

未分类

---

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6439

解析:
根据裴蜀定理知道当且仅当$gcd(C_1,C_2,...,C_k,m)=1$时满足条件,假设固定的数的$gcd$为$a$,不固定的数的个数是$cnt$,那么答案可以表示为:

$$\sum_{m=1}^n \sum_{d|m}f(cnt,d,m)\left[gcd(d,a)=1\right]$$
其中$f(cnt,d,m)$表示有$cnt$个数,每个数范围是$[0,m)$,有多少种方案使这$cnt$个数的$gcd$为$d$.
$$\begin{align*} f(cnt,d,m) &= \sum_{d|i} (m/d)^{cnt}\mu(i/d) \\ &= \sum_{i | m/d} (m/id)^{cnt}\mu(i) \\ \end{align*}$$
设$h(n)=\sum_{i|n}(n/i)^{cnt}\mu(i)$,则$f(cnt,d,m)=h(m/d)$,因为$cnt$是常数,所以先略去.
$$\begin{align*} ans &=\sum_{m=1}^n\sum_{d|m}h(m/d)[gcd(d,a)=1] \\ &= \sum_{m=1}^n\sum_{d|m}h(d)[gcd(m/d,a)=1] \\ &= \sum_{d=1}^n h(d) \sum_{i=1}^{\lfloor n/d \rfloor} [gcd(i,a)==1] \end{align*}$$
考虑$g(n)=\sum_{i=1}^n[gcd(i,a)=1]$.

$$\begin{align*} g(n) &= \sum_{i=1}^n[gcd(i,a)=1] \\ &=\sum_{i=1}^n\sum_{d|gcd(i,a)}\mu(d) \\ &=\sum_{d=1}^n\mu(d)[d|a]\lfloor n/d\rfloor \\ &=\sum_{d|a}\mu(d)\lfloor n/d\rfloor \end{align*}$$

考虑枚举$a$的无平方因子来计算$g(n)$(有平方因子的数的莫比乌斯函数是$0$),设$a$有$pcnt$个质因子,那么枚举的复杂度是$2^{pcnt}$,计算过程还可以考虑剪枝,先对全部的$2^{pcnt}$个数排序,如果当前枚举的数要大于$n$,那么就结束计算,此题中$pcnt$最大是$9$.
那么可以考虑用数论分块来求解原式$\sum_{d=1}^n h(d) \sum_{i=1}^{\lfloor n/d \rfloor} [gcd(i,a)==1].$

接下来需要计算$h(n)=\sum_{i|n}(n/i)^{cnt}\mu(i)$的前$n$项和.
显然这是一个积性函数,考虑与$b(n)=1$做狄利克雷卷积:

$$\begin{align*} (h*b)(n) &=\sum_{d|n}h(d) \\ &= \sum_{d|n}\sum_{i|d}(d/i)^{cnt}\mu(i) \\ &= \sum_{d|n}i^{cnt}\sum_{d'|n/d}\mu(d') \\ &= \sum_{d|n}i^{cnt} [n/d==1] \\ &=n^{cnt} \end{align*}$$

令$s(n)=\sum_{i=1}^nh(i)$,然后:

$$\begin{align*} \sum_{i=1}^n (h*b)(i) &= \sum_{i=1}^nb(i)\sum_{j=1}^{n/i}h(j) \\ &= \sum_{i=2}^ns(n/i) + s(n) \\ &= \sum_{i=1}^ni^{cnt} \end{align*}$$

也就是$s(n)=\sum_{i=1}^ni^{cnt}-\sum_{i=1}^ns(n/i)$.
前面那个可以用自然幂数和做,后面那个直接分块递归计算即可,打表前$n^{2/3}$项并且记忆化,可以在$O(n^{2/3})$求解.

自然数幂和参考文章:https://www.zybuluo.com/yang12138/note/848419
此题用伯努利数来做比较适合.

总复杂度$O(n^{2/3}+512n^{1/2})$,加上记忆化和剪枝复杂度实际要小很多.

参考$AC$代码: https://paste.ubuntu.com/p/9Cs97FSWfN/