配点 : 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... 不是整数。
这种情况不满足部分点约束。