徐老师的连通性问题
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
徐老师最近在复习图论的连通性问题，他决定自己画个图来验证一下自己的实力在这个图中包含 $n$ 个点，每个点拥有一个权值 $a_i$ ，然后徐老师画了很多的边
他仔细一看，发现他画的边竟然隐隐包含着一种规律！
经过他的总结，他发现他画了几种边：
1. 每个点都有一条连向自己的边
2. 他发现对于 $i,j(i < j)$ 两个节点来说，如果 $gcd(a_i,a_j) > 1$，那么就存在一条 $i$ 连向 $j$ 的单向边
3. 对于徐老师来说，$gcd(0,0)=0,gcd(i,0)=i$
现在徐老师打算验证 $q$ 个问题，每次给出 $x,y$，验证第 $x$ 个点能否到达第 $y$ 个点
输入格式
输入第一行包含两个整数 $n,q$，含义如题输入第二行包含 $n$ 个整数 $a_i$，分别表示每个点的权值
接下来 $q$ 行，每行包含两个整数 $x,y$，表示一次询问
对于 $40\%$ 的数据，$n, q \leq 1000,0 \leq a_i \leq 10$
对于 $80\%$ 的数据，$n, q \leq 1000,0 \leq a_i \leq 500$
对于 $100\%$ 的数据，$n, q \leq 10^5, 0 \leq a_i \leq 1000, x \leq y$
输出格式
对于每次询问输出一行，如果可达 $x$ 能到达 $y$ 则输出 "Yes!" 否则输出 "No"样例
5 4
1 3 0 2 1
1 3
2 4
1 4
1 1No!
Yes!
No!
Yes!提示
对于询问 $1$ 到 $3$，由于 $gcd(1,0) = 1$ 所以不可达对于询问 $2$ 到 $4$，由于 $gcd(3,0) = 3,gcd(0,2)=2$ 所以可以按照 $2->3->4$ 的路径到达
23CSP-S秋季提高组模拟赛(6)
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 3
- 开始于
- 2023-10-2 17:15
- 结束于
- 2023-10-12 17:15
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 23
