5 人解决,25 人已尝试。
5 份提交通过,共有 91 份提交。
8.9 EMB 奖励。
单点时限: 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$ 行,每行一个字符串 Yes
或 No
,表示这组询问的答案。
5 2 5 1 7 1 9 1 2 2 4 3 1 3 4 5 2 4
Yes No Yes
3 1000000000 6 998244353 10 0 233 3 1 1 1 2 2 3
Yes No Yes
5 人解决,25 人已尝试。
5 份提交通过,共有 91 份提交。
8.9 EMB 奖励。
创建: 6 年,4 月前.
修改: 5 年,2 月前.
最后提交: 3 年,7 月前.
来源: N/A