#P18494. Sum is Integer

Sum is Integer

Sum is Integer

给定 2N2N 个正整数 (p1,q1,p2,q2,…,pN,qN)(p_1,q_1,p_2,q_2,\ldots,p_N,q_N)。求满足下列条件的整数对 (l,r)(l,r) 的数量:

  • 1≤l≤r≤N1\le l\le r\le N;
  • ∑i=lrpiqi\displaystyle\sum_{i=l}^{r}\frac{p_i}{q_i} 是整数。

输入的分数不保证已经约分。必须按精确有理数判断,不能将接近整数的值当成整数。

输入格式

N
p_1 q_1
p_2 q_2
...
p_N q_N

所有输入值均为整数,且满足:

  • 1≤N≤2×1051\le N\le 2\times10^5;
  • 1≤pi≤qi≤1051\le p_i\le q_i\le10^5,对所有 1≤i≤N1\le i\le N 成立。

本题单组输入,没有额外的测试组数或多组总和限制。

输出格式

输出一个整数,表示满足条件的整数对数量。

样例 1

4
1 6
1 3
1 2
1 2
2

满足条件的整数对为 (1,3)(1,3) 和 (3,4)(3,4),分别有 16+13+12=1\frac16+\frac13+\frac12=1 和 12+12=1\frac12+\frac12=1。

样例 2

5
1 1
2 2
3 3
4 4
5 5
15

所有 1≤l≤r≤51\le l\le r\le5 的整数对均满足条件。

样例 3

2
1 99999
99999 100000
0

两项之和是 $\frac{9999900001}{9999900000}=1.00000000010000100001\ldots$,不是整数。