Q. 「HNOI2016」最小公倍数
「HNOI2016」最小公倍数
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
题目描述
给定一张 个顶点 条边的无向图(顶点编号为 ),每条边上带有权值。所有权值都可以分解成 的形式。
现在有 个询问,每次询问给定四个参数 、、 和 ,请你求出是否存在一条顶点 到 之间的路径,使得路径依次经过的边上的权值的最小公倍数为 。
注意:路径可以不是简单路径。
下面是一些可能有用的定义:
最小公倍数: 个数 的最小公倍数是能被每个 整除的最小正整数。
路径:路径 是顶点序列,满足对于任意 ,节点 和 之间都有边相连。
简单路径:如果路径 中,对于任意 都有 ,那么称路径为简单路径。
输入格式
输入文件的第一行包含两个整数 和 ,分别代表图的顶点数和边数。
接下来 行,每行包含四个整数 、、、 代表一条顶点 和 之间、权值为 的边。
接下来一行包含一个整数 ,代表询问数。
接下来 行,每行包含四个整数 、 、 和 ,代表一次询问。
询问内容请参见问题描述。
输出格式
对于每次询问,如果存在满足条件的路径,则输出一行 Yes
,否则输出一行 No
(注意:第一个字母大写,其余字母小写) 。
样例
4 5
1 2 1 3
1 3 1 2
1 4 2 1
2 4 3 2
3 4 2 2
5
1 4 3 3
4 2 2 3
1 3 2 2
2 3 2 2
1 3 4 4
Yes
Yes
Yes
No
No
数据范围与提示
对于所有的数据,$1 \leq n,q \leq 50000,\ 1 \leq m \leq 100000,\ 0 \leq a,b \leq 10^9 $。
第七届SWPU-ACM老生预选赛
- Status
- Done
- Rule
- ACM/ICPC
- Problem
- 187
- Start at
- 2022-9-19 14:00
- End at
- 2022-10-28 14:00
- Duration
- 936 hour(s)
- Host
- Partic.
- 45