623. 最小公倍数 2

单点时限: 5.0 sec

内存限制: 1024 MB

QQ小方以前不会求最小公倍数,现在他会了,所以他急切的想教会你。

两个或多个整数公有的倍数叫做它们的公倍数,其中除 0 以外最小的一个公倍数就叫做这几个整数的最小公倍数。

我们经常用质因数分解法来求最小公倍数:把每个数分别分解质因数,再把各数中的全部公有质因数提取出来连乘,所得的积就是这几个数的最大公约数。

单单讲给你听肯定是不够的,为了表现自己,QQ小方现在要考考你。

QQ小方决定将问题做再次升级:现在一共有 $n$ 颗星星。星星的闪烁是有规律的。对于第 $i$ 颗星星,它在时刻 $a_i$ 第一次闪烁,之后每隔 $b_i$ 个时刻都会闪烁一次。也就是说,它会在时刻 $a_i, a_i + b_i, a_i + 2 \times b_i,\cdots$ 闪烁,直到时间的尽头。

QQ小方不禁想到:会不会在某一个时刻,所有星星同时闪烁一次呢?经过简单的分析后,QQ小方发现这种情况几乎不可能发生,于是他决定退而求其次:对于 $l, r$ ,他想知道编号在区间 $[l,r]$ 中的星星会不会在某一时刻同时闪烁一次。QQ小方准备了 $q$ 次询问,要对所有询问都求出答案。

输入格式

第一行一个数 $n(1\le n\le 10^6)$ 。

接下来 $n$ 行,每行两个数 $a_i, b_i(0 \le a_i \le 10^9, 1 \le b_i \le 10^7)$

第 $n + 2$ 行一个数 $q(1\le q\le 10^6)$。

接下来 $q$ 行,每行两个数 $l, r$, ($1 \le l \le r \le n$)。

输出格式

输出 $q$ 行,每行一个字符串 YesNo ,表示这组询问的答案。

样例

Input
5
2 5
1 7
1 9
1 2
2 4
3
1 3
4 5
2 4
Output
Yes
No
Yes
Input
3
1000000000 6
998244353 10
0 233
3
1 1
1 2
2 3
Output
Yes
No
Yes

5 人解决,25 人已尝试。

5 份提交通过,共有 91 份提交。

8.9 EMB 奖励。

创建: 6 年,4 月前.

修改: 5 年,2 月前.

最后提交: 3 年,7 月前.

来源: N/A

题目标签