← 返回题目列表

Codeforces · 986/E

E. 王子的问题

中文机器翻译题面 查看原题

让这个问题的主角是最近某部电影中的人物。新复仇者联盟似乎引起了很大的轰动。我没有看过该系列的任何部分,也不太了解其中的英雄,但这不会阻止我在这个问题陈述中使用他们。因此,灭霸和奇异博士正在做他们的超级英雄和超级恶棍的事情,但突然他们偶然发现了一个常规的竞争性编程问题。

给你一棵有 $$$n$$$ 个顶点的树。

每个顶点 $$$v$$$ 都有一个正整数 $$$a_{v}$$$。

您必须回答 $$$q$$$ 查询。

每个查询都有一个 from $$$u$$$ $$$v$$$ $$$x$$$。

您必须计算 $$$\prod_{w \in P} gcd(x, a_{w}) \mod (10^{9} + 7)$$$,其中 $$$P$$$ 是从 $$$u$$$ 到 $$$v$$$ 的路径上的一组顶点。换句话说,您要计算从 $$$u$$$ 到 $$$v$$$ 路径上所有顶点 $$$w$$$ 的 $$$gcd(x, a_{w})$$$ 的乘积。由于它可能很大,请以 $$$10^9+7$$$ 为模进行计算。这里$$$gcd(s, t)$$$表示$$$s$$$和$$$t$$$的最大公约数。

请注意,查询后顶点中的数字不会改变。

我想你对灭霸和奇异博士的超级英雄业务更感兴趣,而不是他们解决问题。所以邀请您代替他们来解决这个问题。

输入

在输入的第一行中有一个整数 $$$n$$$ ($$$1 \le n \le 10^{5}$$$) — 树的大小。

在接下来的 $$$n-1$$$ 行中描述了树的边缘。第 $$$i$$$ 条边由两个整数 $$$u_{i}$$$ 和 $$$v_{i}$$$ ($$$1 \le u_{i}, v_{i} \le n$$$) 描述,它连接顶点 $$$u_{i}$$$ 和 $$$v_{i}$$$。保证具有这些边的图是一棵树。

下一行有 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_{v} \le 10^{7}$$$)。

下一行有一个整数 $$$q$$$ ($$$1 \le q \le 10^{5}$$$) — 查询数。

在接下来的 $$$q$$$ 行中描述了查询。每个查询由三个整数 $$$u_{i}$$$、$$$v_{i}$$$ 和 $$$x_{i}$$$ ($$$1 \le u_{i}, v_{i} \le n$$$, $$$1 \le x_{i} \le 10^{7}$$$) 描述。

输出

打印 $$$q$$$ 数字 — 按照输入中给出的顺序查询的答案。打印每个答案模 $$$10^9+7 = 1000000007$$$。将每个数字打印在单独的行上。

示例

输入 #1

4
1 2
1 3
1 4
6 4 9 5
3
2 3 6
2 3 2
3 4 7

输出 #1

36
4
1

输入 #2

6
1 2
2 3
2 4
1 5
5 6
100000 200000 500000 40000 800000 250000
3
3 5 10000000
6 2 3500000
4 1 64000

输出 #2

196000
12250
999998215