[BZOJ 5019] 玄学做法
zhoutb2333
·
·
个人记录
复杂度是 O(\sqrt{L}+d(L)^2+d_3(L)) 。
其中 d_3(L)= \sum \limits _{i_1|L} \sum \limits _{i_2|i_1} \sum \limits _{i_3|i_2} 1 。就是约数的约数的约数个数。
用EOJ卡卡常能跑 n,L \le 10^{13} ，\bf 2.5s 出结果。
做法大概是：
设 f(x,y) 为从 1 ~ n 中选出一些数字，使得 gcd=x,lcm=y 的方案数，g(x,y) 为从 1 ~ n 中选出一些数字，使得 x|gcd,lcm|y 的方案数。
容易发现假如不加任何“固定必须选 k ”的限制，那么 f(G,L) 就是要输出的答案。
发现这个 g(x,y) 比 f(x,y) 好算多了：
令 S=\{ a_i:\text{满足}x|a_i|y \} ，那么 g(x,y) 就等于 2^{|S|}-1 。因为任选一个 S 的子集，gcd 肯定是 x 的倍数，lcm 肯定是 y 的约数。
容易发现 g(x,y)=\sum \limits _{x|z|w|y} f(z,w) 。于是莫比乌斯反演告诉我们 f(z,w)= \sum \limits _{z|x|y|w} g(x,y) \times \mu(\frac{x}{z}) \times \mu(\frac{w}{y}) 。这就好搞了。
假如说我们先不管“固定选 k ”，那么 f(G,L) 就是 \sum \limits _{G|x|y|L} (2^{tot[x][y]}-1) \times \mu(\frac{x}{G}) \times \mu(\frac{L}{y}) 。其中 tot[x][y] 表示 1 ~ n 里满足 x|a|y 的 a 的个数。
那么如果我们再固定选上一个数字，比如是 k 。那么方案数就变成了 \sum \limits _{G|x|k|y|L} 2^{tot[x][y]-1} \times \mu(\frac{x}{G}) \times \mu(\frac{L}{y}) 。
最坏情况下我们要对每个满足 G|k|L 的 k 算一遍上一个式子。那么我们可以设计一个算法：
- 先枚举一个 x ，使得 G|x 。
- 然后枚举一个 k ，使得 x|k ，这时候我们要统计给 ans[k] 的贡献。
- 最后枚举一个 y ，使得 k|y|L ，我们给 ans[k] 加上刚才那个式子就行了。
计算 tot[x][y] 时可以采用同样的枚举顺序（ x,k,y ），然后 tot[x][y]+=(k \le n) 即可。
要想快速枚举一个数字的倍数，我们需要用 vector 。 要想去掉一个 \log ，我们还需要用一些奇技淫巧。具体细节见代码。
总复杂度就是一开始写的了。
代码的数组是按照 n,L \le 10^{13} 开的。
https://paste.ubuntu.com/p/FdHDvRwmPJ/