A2307. 最小公倍数
编程题
省选/NOI-
知识点
题目描述
给定一张 $N$ 个顶点 $M$ 条边的无向图(顶点编号为 $1,2,\ldots,n$)，每条边上带有权值。所有权值都可以分解成 $2^a\times 3^b$ 的形式。
现在有 $q$ 个询问，每次询问给定四个参数 $u,v,a$ 和 $b$，请你求出是否存在一条顶点 $u$ 到 $v$ 之间的路径，使得路径依次经过的边上的权值的最小公倍数为 $2^a\times 3^b$。
注意：路径可以不是简单路径。
下面是一些可能有用的定义，如果与其它地方定义不同，在本题中以下面的定义为准：
最小公倍数： $k$ 个数 $a_1 , a_2, \ldots, a_k$ 的最小公倍数是能被每个 $a_i$ 整除的最小正整数。
路径：顶点序列 $P \colon P_1,P_2,\ldots,P_$ 是一条路径，当且仅当 $k \geq 2$，且对于任意 $1 \leq i < k$ ，节点 $P_i$ 和 $P_{i+1}$ 之间都有边相连。
简单路径：如果路径 $P \colon P_1,P_2,\ldots,P_k$ 中，对于任意 $1 \leq s \neq t \leq k$ 都有 $P_s \neq P_t$ ，那么称 $P$ 为简单路径。
现在有 $q$ 个询问，每次询问给定四个参数 $u,v,a$ 和 $b$，请你求出是否存在一条顶点 $u$ 到 $v$ 之间的路径，使得路径依次经过的边上的权值的最小公倍数为 $2^a\times 3^b$。
注意：路径可以不是简单路径。
下面是一些可能有用的定义，如果与其它地方定义不同，在本题中以下面的定义为准：
最小公倍数： $k$ 个数 $a_1 , a_2, \ldots, a_k$ 的最小公倍数是能被每个 $a_i$ 整除的最小正整数。
路径：顶点序列 $P \colon P_1,P_2,\ldots,P_$ 是一条路径，当且仅当 $k \geq 2$，且对于任意 $1 \leq i < k$ ，节点 $P_i$ 和 $P_{i+1}$ 之间都有边相连。
简单路径：如果路径 $P \colon P_1,P_2,\ldots,P_k$ 中，对于任意 $1 \leq s \neq t \leq k$ 都有 $P_s \neq P_t$ ，那么称 $P$ 为简单路径。
输入格式
输入文件的第一行包含两个整数 $N$ 和 $M$，分别代表图的顶点数和边数。
接下来 $M$ 行，每行包含四个整数 $u,v,a,b$ 代表一条顶点 $u$ 和 $v$ 之间、权值为 $2^a\times 3^b$ 的边。
接下来一行包含一个整数 $q$，代表询问数。
接下来 $q$ 行，每行包含四个整数 $u,v,a$ 和 $b$，代表一次询问。询问内容请参见问题描述。
接下来 $M$ 行，每行包含四个整数 $u,v,a,b$ 代表一条顶点 $u$ 和 $v$ 之间、权值为 $2^a\times 3^b$ 的边。
接下来一行包含一个整数 $q$，代表询问数。
接下来 $q$ 行，每行包含四个整数 $u,v,a$ 和 $b$，代表一次询问。询问内容请参见问题描述。
输出格式
对于每次询问，如果存在满足条件的路径，则输出一行
Yes，否则输出一行 No（注意：第一个字母大写，其余字母小写）。输入输出样例
输入 #1
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
输出 #1
Yes Yes Yes No No
说明/提示
$1\le n,q\le 5\times 10^4$，$1\leq m\leq 10^5$，$0\leq a,b\leq 10^9$。