数论+图论,妙不可言
# 题面
给定 $A,B,C$,求:
数据规模:$A,B,C\le 2\times10^5$。
# 解析
显然 $A,B,C$ 三者等价,不妨设 $A$ 是最大的
关于 $\sigma_0$,有一个众所周知(比如我就不知道) 的结论:
三个数也是一样的,
于是直接代回我们要求的式子:
记 $[a,b]$ 为 $a, b$ 的最小公倍数。两数互质的条件可以进行反演:
定义 $f_b(a)$ 如下:
可以 $O(A\ln A)$ 预处理出 $f_A(x), f_B(x), f_C(x)$,于是要求的答案就是
但是我们发现这一波推导过后并没有什么用,直接算还是 $O(A^3)$ 的。只是可以进行一些剪枝?
- $\mu(a),\mu(b),\mu(c)$ 都必须非零,这样可以去掉很多无用的枚举;
- $\max\big\{[a,b],[b,c],[c,a]\big\}\le A$,好像也可以减掉一些枚举。
这些剪枝足够吗?如果仍然三重 for
循环枚举,这样剪枝过后还是过不了。但是注意到这两个限制,第二个限制与两个变量相关,类似于图上的边。
- 条件一限制了图上的点的 $\mu$ 非零;
- 条件二表示,若 $[a,b]\le A$,则图上存在 $(A,B)$ 这条无向边。
恰巧的是,我们计算的是一个三元组,体现在图上就是一个三元环!
记 $M$ 为图的边数,我们可以用下面的方法 $O(M\sqrt{M})$ 地枚举所有三元环:
- 统计每个点的度数,记作 $deg_u$;
- 给边定向,由度数大的点指向度数小的,若度数相等,则编号大的指向编号小的(编号小指向编号大也无所谓,反正要求二元组 $(\deg_u,u)$ 的大小比较唯一且具有传递性);
- 枚举点 $u$:
- 标记 $u$ 连出的所有点 $v$;
- 枚举 $u$ 连出的点 $v$:
- 枚举 $v$ 连出的点 $w$,若 $w$ 有标记,则找到三元环。
三元环计数正确性、时间复杂度的证明
根据边定向的规则,因为数对 $(deg_u, u)$ 的大小关系具有传递性且唯一确定,所以定向后的图一定是 DAG。
这意味着三元环一定是由 $u\to v\to w$ 和 $u\to w$ 构成的。且根据我们的枚举方式,这样的三元环仅能在枚举 $u$ 时计算到。所以计数不重不漏,正确性有保证。
时间复杂度的证明类似分块。首先,标记点的时间复杂度为 $O(M)$,因为每条边只会遍历一次,不是复杂度的瓶颈。
然后关注枚举的 $u\to v\to w$ 的中心点 $v$:
- 若 $deg_v\le\sqrt{M}$,则 $w$ 只有 $O(\sqrt{M})$ 个,$(u,v)$ 最多 $O(M)$ 个,则所有此类点 $v$ 的复杂度为 $O(M\sqrt{M})$;
- 若 $deg_v\gt\sqrt{M}$,因为 $u$ 连向 $v$,则 $deg_u\ge deg_v\gt\sqrt{M}$,这样的 $u$ 只有 $O(\sqrt{M})$ 个,而 $(v,w)$ 仅有 $O(M)$ 个;则所有此类 $v$ 点的复杂度也为 $O(M\sqrt{M})$。
总复杂度 $O(M\sqrt{M})$。
回到这道题上来,我们就是要枚举图上的一个三元环然后计算答案。那么这个图的边数多大呢?打个表发现 $O(M\sqrt{M})$ 能过……(反正我不会证)
于是按上述方法枚举即可。
注意实际上枚举的不止有三元环,还存在 $a=b$ 甚至是 $a=b=c$ 的情况,不过这两种都可以直接暴力枚举,不是很重要。
# 源代码
1 | /*Lucky_Glass*/ |
THE END
Thanks for reading!
怎知晓 有人 玩世不恭掩愁肠
取次花丛懒望 等剪烛西窗
怎知晓 有人 独为异客在异乡
嘴上逞强终不敢 举头看月光
——《从前有个衔玉教》By 星葵/鲜洋芋/溱绫西陌
> Link 【0412乐正绫诞生祭】从前有个衔玉教-Bilibili