B. 连通
1s 512MB
题目描述
给定一棵 $n$ 个点的树，第 $i$ 个节点有权值 $a_i$。一个非空连通块合法当且仅当：
- 连通块内点权值的最大公约数等于 $X$；
- 连通块内点权值的最小公倍数等于 $Y$。
求合法非空连通块个数对 $10^9+7$ 取模后的结果。
输入格式
第一行三个整数 $n,X,Y$，含义见题目描述。接下来 $n-1$ 行每行两个数 $u,v$，描述树上的一条边。
输出格式
一行一个数，表示合法的连通块个数对 $10^9+7$ 取模后的结果。
样例 #1
输入样例 #1
3 1 2
1 2 2
1 2
1 3输出样例 #1
3说明
有三种方案 $\{1,2\},\{1,3\},\{1,2,3\}$ 。
对于前 $10\%$ 的数据：$Y=1$。
对于前 $20\%$ 的数据：$Y\leq 10^3$。
对于前 $30\%$ 的数据：$Y\leq 10^5$。
对于前 $40\%$ 的数据：$Y\leq 10^7$。
对于前 $60\%$ 的数据：$Y\leq 10^{10}$。
对于全部数据，保证 $1\leq n\leq 10^3,1\leq a_i,X,Y\leq 10^{18},X\mid a_i,a_i\mid Y$，$\mu(Y)\neq 0$ 且 $Y$ 不存在大于 $50$ 的质因子。