冷冻沙丁鱼 – 题解

冷冻沙丁鱼 – 题解

问题描述:

钓了N条沙丁鱼,每条沙丁鱼的美味度为A,鲜度为B。现要将沙丁鱼存放到冰箱里冷冻。但是沙丁鱼的冷冻是有特殊要求的:如果有两条沙丁鱼i,j的美味度和鲜度满足: \( A_i A_j + B_i B_j = 0 \),则这两条鱼会急速腐化,导致整个冰箱中的鱼都坏掉,所以不能让这样的鱼同时冷冻在冰箱中。
分别给出N条沙丁鱼的美味度\( A_i \) 与鲜度 \( B_i \),计算有多少种选法可以正常进行冷冻沙丁鱼而不致其腐化。(结果可能较大,所以输出对1000000007余的值)

\( 1 \le N \le 2 \times 10^5 \)
\( -2 \times 10^{18} \le A_i,B_i \le 2 \times 10^{18} \)

题目序号abc168_e

测试样例

输入1

3
1 2
-1 1
2 -1

输出1

5

输入2

10
3 2
3 2
-1 1
2 -1
-3 -9
-8 12
7 7
8 1
8 2
8 4

输出2

479

思路

\( (A_i,B_i)=(0,0) \)的沙丁鱼会和任意的沙丁鱼组合都会腐化,就有只选一只\( (A_i,B_i)=(0,0) \)的沙丁鱼,和\( (A_i,B_i)=(0,0) \)一只都不选这两类,显然,前者的选法和\( (A_i,B_i)=(0,0) \)的沙丁鱼数量一样。接下来主要对后者情况讨论,即\( (A_i,B_i) \neq (0,0) \).

   定义沙丁鱼的“斜率”为\(\frac{A_i}{B_i} \),并且这个数值要表示为分数约分后的结果。 更具体的规则如下所示

  • \( B_i=0\)时,斜率为1/0
  • \(B_i >0\)时,斜率为\(\frac{A_i}{\gcd(A_i,B_i)} / \frac{B_i}{\gcd(A_i,B_i)} \)
  • \(B_i >0\)时,斜率为\(\frac{A_i}{\gcd(A_i,B_i)} / \frac{B_i}{\gcd(A_i,B_i)} \)

以下的情况中描述了斜率和相互腐化的关系

  • 斜率1/0的沙丁鱼会与斜率为0/1的发生腐化,反之亦然
  • 斜率为a/b( \(a, b \neq 0\) )的沙丁鱼会与斜率为-b/a的发生腐化,反之亦然

例如以下几组斜率是相互被腐化的

\[ 1/0 \leftarrow \rightarrow 0/1  \]
\[ 5/3 \leftarrow \rightarrow -3/5  \]
\[ 2/1 \leftarrow \rightarrow -1/2  \]

因此,可以使用组成“沙丁鱼腐化斜率数对”(共N个),把斜率出现的个数存储在关联数组(例如C++的map或Python的dict)当中,然后进行计数即可。 

请小心数据溢出。

由于此题\( (A_i,B_i) \)的数值可能很大,如果用相应的小数代替分数,即使是用long double精度仍然不够。

发表评论

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