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 翻译