← 返回题目列表

AtCoder · judge_update_202004_d

D. 计算 GCD

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

配点 : 400 点

問題文

长度 小于或等于 N 整数序列 给出 A_1, A_2, \cdots, A_N 。

Q 的 您可以创建一个包含 1 的整数 给出了 S_1, S_2, \cdots, S_Q ,所以i = 1, 2, \cdots, Q 如果 X = S_i 则求答案。

  • 第一个整数 有 X 。j = 1, 2, \cdots, N 的顺序, 执行替换为X 该值应乘以 \gcd(X, A_j) 的操作。j 第二次操作后立即 X = 1 似乎是 j 存在那么这样 j 的最小值,如果不存在,则最终 找到 X 的值。

制約

  • 1 \leq N, Q \leq 10^5
  • 1 \leq A_i \leq 10^9
  • 1 < S_i \leq 10^9
  • 所有输入均为整数

注記

2 个 0 的整数 给出了 X, Y 的最大公约数 请他们了解 \gcd(X, Y) 代表。

std::gcd 在 C++ 中可用。

在 Python 中,fractions.gcd 已更改为 math.gcd。 关于


入力

输入是按以下格式从标准输入给出的。

N Q
A_1 A_2 \cdots A_N
S_1 S_2 \cdots S_Q

出力

i = 1, 2, \cdots, Q 关于 X = S_i 按顺序输出答案。


入力例 1

4 3
6 12 6 9
4 6 3

出力例 1

4
3
3
  • i = 1 时,X 是开始 在 4 。4 操作之后,每个 X = 2, 2, 2, 1 变为 通过4 操作后的第一次 X = 1 所以 请输出 4 输出。

  • i = 2 时,X 是开始 在 6 。4 操作之后,每个 X = 6, 6, 6, 3 变为 通过4 操作之后 X \neq 1 ,所以最后 是 X 的值 3 输出。

  • i = 3 时,X 是开始 在 3 。4 操作之后,每个 X = 3, 3, 3, 3 变为 通过4 操作之后 X \neq 1 ,所以最后 是 X 的值 3 输出。


入力例 2

4 3
4 6 2 1
3 2 1000000000

出力例 2

1
4
4