A14099 | $GCD of an Array$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

You are given an array $a$ of length $n$ . You are asked to process $q$ queries of the following format: given integers $i$ and $x$ , multiply $a_i$ by $x$ . After processing each query you need to output the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of all elements of the array $a$ . Since the answer can be too large, you are asked to output it modulo $10^9+7$ .

The first line contains two integers — $n$ and $q$ ( $1 \le n, q \le 2 \cdot 10^5$ ). The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $1 \le a_i \le 2 \cdot 10^5$ ) — the elements of the array $a$ before the changes. The next $q$ lines contain queries in the following format: each line contains two integers $i$ and $x$ ( $1 \le i \le n$ , $1 \le x \le 2 \cdot 10^5$ ).

Print $q$ lines: after processing each query output the GCD of all elements modulo $10^9+7$ on a separate line.

输入 #1

输出 #1

2
2
6

C++ 编辑器

输入

输出