HBC20118[HNOI2016]最小公倍数题解

素流年算法基础篇 2023-11-15 08:44:01 42 0

想要检验自己的编程水平？来试试全网最全C++题库，让您在挑战中不断进步。

给定一张N个顶点M条边的无向图(顶点编号为1,2,…,ak的最小公倍数是能被每个ai整除的最小正整数，路径：路径P:P1,P2,…,Pk是顶点序列，满足对于任意1 ≤ i < k，节点Pi和Pi+1之间都有边相连，简单路径：如果路径P:P1,P2,…

给定一张N个顶点M条边的无向图(顶点编号为1,2,…,n)，每条边上带有权值。所有权值都可以分解成2^a*3^b 的形式。现在有q个询问，每次询问给定四个参数u、v、a和b，请你求出是否存在一条顶点u到v之间的路径，使得路径依次经过的边上的权值的最小公倍数为2^a*3^b。注意：路径可以不是简单路径。下面是一些可能有用的定义：最小公倍数：K个数a1,a2,…,ak的最小公倍数是能被每个ai整除的最小正整数。路径：路径P:P1,P2,…,Pk是顶点序列，满足对于任意1 ≤ i < k，节点Pi和Pi+1之间都有边相连。简单路径：如果路径P:P1,P2,…,Pk中，对于任意1 ≤ s≠t ≤ k都有Ps≠Pt，那么称路径为简单路径。