AT_ttpc2023_m Sum is Integer

给定 $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} $ 是整数。

输入按以下格式从标准输入读入： > $N$ $p_1$ $q_1$ $p_2$ $q_2$ $\dots$ $p_N$ $q_N$

请输出答案。

### 部分分 - 对于满足额外约束 $q_i \le 30\ (1\le i\le N)$ 的数据集，计 20 分。 ### 样例解释 1 满足条件的 $ (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 所有满足 $ 1 \le l \le r \le 5 $ 的整数对 $ (l, r) $ 都满足条件。此组也满足部分分约束。 ### 样例解释 3 $ \displaystyle\sum_{i=1}^{2}\dfrac{p_i}{q_i}=\dfrac{1}{99999}+\dfrac{99999}{100000}=\dfrac{9999900001}{9999900000}=1.00000000010000100001... $ 不是整数。 这一组数据不满足部分分约束。 ### 数据范围 - 输入均为整数 - $ 1\le N\le 2\times 10^5 $ - $ 1\le p_i\le q_i\le 10^5\ (1\le i\le N) $ 由 ChatGPT 5 翻译