PE530 Divisors

时间:
6.18

题意:
给定,求

题解:
推式子,%Cab。

于是枚举计算右边的式子。
复杂度为:

YMD另解:
原式

于是原式

可以计算,那么如何计算


考虑枚举的质因子递推计算,设的一个质因子为

计算递归的复杂度为

总复杂度即为

其他:
主要是要推对式子,然后把重要的东西提到前面来,发现有一个可以合并的两项。
YMD的想法比较厉害,首先容斥一维成,然后对于该gcd求和的函数,依次加入质因子,然后复杂度很资瓷。
神犇随便都能推出一堆解法,然而我一个都推不出啊。。。

SPOJ DIVCNT2

时间:
6.18

题意:
给定,求

题解:
推式子,%Cab。
洲阁论文杜教筛例题。

,则,其中表示的不同质因子数。
可以通过质因子分解的方式计算除数函数来证明。

于是我们有:

其中第二步、第三步可以通过他们的实际意义来推得。
线性筛预处理,然后记忆化递归算上面三个式子,复杂度是

Cab做法是,将第二个式子代入第一个式子,得到:
由上面第三个式子,计算的复杂度是
计算复杂度是的。
运用杜教筛复杂度证明,预处理后复杂度为

其他:
灵活运用每个式子的实际意义(这种神奇转换怎么看得出啊)。

洲阁筛学习

时间:
6.20

首先是积性函数的一些定义:积性函数,以及当是一个质数时的特殊情况。其中是关于的低次多项式。
我们需要求
一个数至多含有一个的因子,于是我们一个个加入以内的质因子。
于是我们可以将其变为$$\sum_{i=1}^{\sqrt{n}} F(x)= \sum_{x=1,x不含> \sqrt{n}因子} F(x) \times (1 + \sum_{\sqrt{n} < p \leq \frac{n, p为质数}{x}} G(p))$$
于是我们可以将其分成段计算,每一段计算:
$$\sum_{\sqrt{n} < p \leq y,p为质数}G(p),\sum_{\lfloor \frac{n}{x} \rfloor=y,x没有>\sqrt{n}因子}F(x)$$

大概就是将质因子一个个地加入记录两维,一维是质因子个数,一维是范围限制。第二维的状态量是
然后加一个优化,我们只需要在转移的时候枚举的质数,的部分贡献可以直接算出来。
于是复杂度变为了

BZOJ4555 sum

时间:
6.21

题意:

其中,是第二类斯特林数。

题解:
实际意义为:将个不同元素放入个无异盒子的方案数。
若盒子有区别,则方案数为,而我们可以通过容斥来计算这个方案数。


也就是斯特林数反演。
代入原式、将化开即可得到卷积形式。

第一类斯特林数
,将个不同元素划分成个非空圆周排列的方案数,
第二类斯特林数
,将个不同元素放入个无异盒子的方案数,
斯特林数反演:

Comments

comments powered by Disqus