Atcoder ABC 168

作者: ffacs 分类: Atcoder 发布时间: 2020-05-24 18:02

E

题意

给定$n \le 2e5$ 个二元组 $(a,b) -1e18\le a,b\le 1e18$ ,若两个二元组 $i,j$ 满足 $a_ia_j+b_ib_j=0$ ,则 $i,j$ 不能同时存在,问有多少种选择方法。

解法

这个形式可以看成是点乘的形式,那么二元组就对应二维平面上的一个向量了。也就是说不能存在两个向量相互垂直。我们可以先把向量约分成互质的形式,然后将在同一条直线上的向量计数。然后一个十字(相互垂直)的选择方式为分别选择一条的方案相加再减一。还有一个特殊的向量需要分开来处理即$(0,0)$。

发表评论

电子邮件地址不会被公开。 必填项已用*标注