← 返回题目列表

AtCoder · ttpc2023_m

M. 总和为整数

中文机器翻译题面 查看原题

配点 : 100 点

問題文

2N 正整数 找出满足以下条件的 (p_1,q_1,p_2,q_2,\dots ,p_N,q_N) 。 对于

1\le l\le r\le N 的整数集合 查找 (l,r) 的数量。

  • \displaystyle\sum_{i=l}^{r}\dfrac{p_i}{q_i} 是一个整数。

制約

  • 所有输入均为整数
  • 1\le N\le 2\times 10^5
  • 1\le p_i\le q_i\le 10^5\ (1\le i\le N)

部分点

  • 附加限制 如果正确答案是满足 q_i \le 30\ (1\le i\le N) 的数据集 给出 20 点。 如果您正确回答了所有满足

入力

输入是按以下格式从标准输入给出的。

N
p_1 q_1
p_2 q_2
\vdots
p_N q_N

出力

打印答案。 来自


入力例 1

4
1 6
1 3
1 2
1 2

出力例 1

2

满足条件 (l,r) 是 您也可以写 (1,3),(3,4) 可以得到第 2 一。事实上,

  • \displaystyle\sum_{i=1}^{3}\dfrac{p_i}{q_i}=\dfrac{1}{6}+\dfrac{1}{3}+\dfrac{1}{2}=1
  • \displaystyle\sum_{i=3}^{4}\dfrac{p_i}{q_i}=\dfrac{1}{2}+\dfrac{1}{2}=1

。这种情况满足部分点约束。 所有满足


入力例 2

5
1 1
2 2
3 3
4 4
5 5

出力例 2

15

1\le l\le r\le 5 的整数对 (l,r) 满足条件。这种情况也满足部分点约束。


入力例 3

2
1 99999
99999 100000

出力例 3

0

\displaystyle\sum_{i=1}^{2}\dfrac{p_i}{q_i}=\dfrac{1}{99999}+\dfrac{99999}{100000}=\dfrac{9999900001}{9999900000}=1.00000000010000100001... 不是整数。

这种情况不满足部分点约束。