P3247 [HNOI2016] Least Common Multiple

Given an undirected graph with $N$ vertices and $M$ edges (the vertices are numbered $1, 2, \ldots, N$). Each edge has a weight, and every weight can be factorized as $2^a \times 3^b$. There are $q$ queries. In each query, you are given four parameters $u, v, a$, and $b$. Please determine whether there exists a path from vertex $u$ to vertex $v$ such that the least common multiple of the weights of the edges traversed along the path is exactly $2^a \times 3^b$. Note: The path does not have to be simple. Below are some definitions that may be useful. If they differ from other sources, use the definitions below for this problem: Least common multiple: The least common multiple of $k$ numbers $a_1, a_2, \ldots, a_k$ is the smallest positive integer that is divisible by each $a_i$. Path: A vertex sequence $P \colon P_1, P_2, \ldots, P_k$ is a path if and only if $k \geq 2$, and for any $1 \leq i < k$, there is an edge between $P_i$ and $P_{i+1}$. Simple path: If in a path $P \colon P_1, P_2, \ldots, P_k$, it holds that $P_s \neq P_t$ for any $1 \leq s \neq t \leq k$, then $P$ is called a simple path.

The first line contains two integers $N$ and $M$, the number of vertices and edges of the graph. Each of the next $M$ lines contains four integers $u, v, a, b$, representing an edge between vertices $u$ and $v$ with weight $2^a \times 3^b$. The next line contains an integer $q$, the number of queries. Each of the next $q$ lines contains four integers $u, v, a$, and $b$, representing one query. See the problem description for details.

For each query, output one line: `Yes` if such a path exists, otherwise output `No` (note: the first letter is uppercase, the rest are lowercase).

Constraints: $1 \leq N, q \leq 5 \times 10^4$, $1 \leq M \leq 10^5$, $0 \leq a, b \leq 10^9$. Translated by ChatGPT 5