离赛时ac就差了三行代码啊啊啊…十分的遗憾（虽然杭电崩溃事件对能不能过这道题没什么影响，但我就是要甩锅给hdu嘤嘤嘤）。
一开始看到这个题其实我觉得是线性筛就可以解决的，直到我发现还有一种特殊情况是需要亚线性筛才能解决…（其实我几乎没做过杜教筛的题呢…这也导致了bug多得起飞直到结束也没调完…）
定义 $f(m)$ 函数为：对于一组已知的序列$A_1,A_2,…,A_k$,满足以下条件的$C$序列（$C_1,C_2,…,C_K$）的个数：
条件1：如果$A_i=-1$，那么$C_i$可以是 $[0,m)$ 之间的任意整数，否则$C_i$需满足 $C_i \equiv A_i(mod \ m)$ 。
条件2：关于 $x_1,x_2,…,x_k$ 的同余方程组 $\Sigma_{i=1}^k C_ix_i \equiv 1(mod \ m)$ 有整数解。
给你一个$T$代表有$T$组样例；
对于每组样例给出一个$k$和一个$n$，接着给出$k$个元素的序列$A_1,A_2,…,A_k$,计算 $\Sigma_{m=1}^n f(m)$ 的值（对 $1e9+7$ 取模）。
$T \leq 100,k \in [1,50],n \in [1,10^9],A_i \in [-1,10^9] \ ( \forall \ i \in [1,k] )$
那么首先很显然的是，同余方程 $\Sigma_{i=1}^k C_ix_i \equiv 1(mod \ m)$ 有解等价于 $gcd(C_1,C_2,…,C_k,m)=1$，所以 $f(m)$ 转化为了：
$$\Sigma_{C_1}\Sigma_{C_2}…\Sigma_{C_k}[gcd(C_1,C_2,…,C_k,m)=1]$$
考虑两种情况，一种是 $C_1,C_2,…,C_k$ 中有部分是 $-1$ ，剩下部分为具体的数；另一种是 $C_1,C_2,…,C_k$ 均为 $-1$ 。我们先来考察第一种情况。
情况1：$C_1,C_2,…,C_k$ 中有部分是 $-1$。
不妨将$C_1,C_2,…,C_k$ 中 $-1$ 的个数记为$t$ , 将不为 $-1$ 的数的 $gcd$ 记为 $w$ 。那么原式转化为
$$\Sigma_{C_1=0}^{m-1}\Sigma_{C_2=0}^{m-1}…\Sigma_{C_t=0}^{m-1}[gcd(C_1,C_2,…,C_t,w,m)=1]$$
其实等价于
$$\Sigma_{C_1=1}^{m}\Sigma_{C_2=1}^{m}…\Sigma_{C_t=1}^{m}[gcd(C_1,C_2,…,C_t,w,m)=1]$$
化简得到：
$$\Sigma_{C_1=1}^{m}\Sigma_{C_2=1}^{m}…\Sigma_{C_t=1}^{m}\Sigma_{d \mid gcd(C_1,C_2,…,C_t,w,m)} \mu(d)$$
考虑枚举 $d$ ，就有：
$$\Sigma_{d=1}^{m}\mu(d)[d \mid gcd(w,m)] \ \Sigma_{C_1=1}^{m}\Sigma_{C_2=1}^{m}…\Sigma_{C_t=1}^{m}[d \mid gcd(C_1,C_2,…,C_t)]$$
也就是
$$\Sigma_{d \mid gcd(w,m)}\mu(d) {(\frac{m}{d} )}^t$$
现在考虑 $\Sigma_{m=1}^n f(m)$ :
$$
\begin{equation}
\begin{split}
\Sigma_{m=1}^n f(m) &= \Sigma_{m=1}^n\Sigma_{d \mid gcd(w,m)}\mu(d) {(\frac{m}{d} )}^t\\
&=\Sigma_{d \mid w}\mu(d) \Sigma_{k=1}^{k \leq \lfloor \frac{n}{d}\rfloor}k^t
\end{split}
\end{equation}
$$
$w$ 的范围只有 $[1,10^9]$ , 所以可以 $O(\sqrt{w})$ 分解他，然后枚举他的所有因子，并且在搜索的过程中获得他每个因子的莫比乌斯函数值。而后半部分可以通过预处理伯努利数 用求解自然数幂和的方法在 $O(t)$ 的复杂度内计算，故总复杂度应该为$O(\sqrt{w}+t*d(w))$，可以接受。
接下来考虑情况2：$C_1,C_2,…,C_k$ 全部是 $-1$。
在这种情况下， $f(m)$ 退化为：
$$
\Sigma_{C_1=0}^{m-1}\Sigma_{C_2=0}^{m-1}…\Sigma_{C_k=0}^{m-1}[gcd(C_1,C_2,…,C_k,m)=1]
$$
熟悉的处理方式：
$$
\begin{equation}
\begin{split}
f(m) &= \Sigma_{C_1=0}^{m-1}\Sigma_{C_2=0}^{m-1}…\Sigma_{C_k=0}^{m-1}[gcd(C_1,C_2,…,C_k,m)=1]\\
&= \Sigma_{C_1=1}^{m}\Sigma_{C_2=1}^{m}…\Sigma_{C_k=1}^{m}\Sigma_{d \mid gcd(C_1,C_2,…,C_k,m)}\mu(d)\\
&=\Sigma_{d \mid m}\mu(d) \ \Sigma_{C_1=1}^{m}\Sigma_{C_2=1}^{m}…\Sigma_{C_k=1}^{m}[d \mid gcd(C_1,C_2,…,C_k)]\\
&=\Sigma_{d \mid m}\mu(d)(\frac{m}{d})^k
\end{split}
\end{equation}
$$
那么 $\Sigma_{m=1}^nf(m)$ 就有：
$$
\begin{equation}
\begin{split}
\Sigma_{m=1}^n f(m) &= \Sigma_{m=1}^n\Sigma_{d \mid m}\mu(d)(\frac{m}{d})^k\\
&= \Sigma_{d=1}^{n}\mu(d)\Sigma_{t=1}^{\lfloor \frac{n}{d} \rfloor}t^k
\end{split}
\end{equation}
$$
这里出现了 $\lfloor \frac{n}{d} \rfloor$ ，那么我们考虑分段加速，即：枚举 $\lfloor \frac{n}{d} \rfloor$ 的取值，这样的话只需要枚举 $O(\sqrt{n})$ 个值即可。
考虑当 $\lfloor \frac{n}{d} \rfloor=a$ 时，对应的 $\mu(d)$ 为 $\mu(\lfloor \frac{n}{a+1} \rfloor+1) + \mu(\lfloor \frac{n}{a+1} \rfloor+2) + … + \mu(\lfloor \frac{n}{a} \rfloor)$ ，也就是 $\Sigma_{t=\lfloor \frac{n}{a+1} \rfloor+1}^{\lfloor \frac{n}{a} \rfloor}\mu(t)$，亦即 $\Sigma_{t=1}^{\lfloor \frac{n}{a} \rfloor}\mu(t)-\Sigma_{t=1}^{\lfloor \frac{n}{a+1} \rfloor}\mu(t)$ 。所以对于$n$，我们只需要预处理出 $\mu(x)$ 在 $\lfloor \frac{n}{1} \rfloor,\lfloor \frac{n}{2} \rfloor,…,\lfloor \frac{n}{n} \rfloor$ 处的前缀和即可。而根据经典的 杜教筛计算 $\mu(x)$ 前缀和 的方法中，式子 $\Sigma_{i=1}^n\mu(i) = 1-\Sigma_{d=2}^n\Sigma_{j=1}^{\lfloor \frac{n}{d} \rfloor}\mu(j)$ 恰好可以在 $O(n^\frac{2}{3})$ 内筛出 $\mu(x)$ 在 $\lfloor \frac{n}{1} \rfloor,\lfloor \frac{n}{2} \rfloor,…,\lfloor \frac{n}{n} \rfloor$ 处的前缀和，于是这种情况也被解决了，复杂度为 $O(n^\frac{2}{3}+k \sqrt{n})$。
最后要注意一下当 $C_1,C_2,…,C_k$ 中只有 $-1$ 和 $0$ 的时候，情况一会退化为情况2就可以了，总的复杂度应该是 $O(max(n^\frac{2}{3}+k \sqrt{n},\sqrt{n}+t*d(n))$
最后贴上ac代码：
|
|
