Array and Gahui
Time limit2sMemory limit512 MB
Process point updates on an array and after each one count index pairs whose two values have GCD greater than one.
- Level
Medium6 of 10
- Topics
- Hash map, Number theory, Math, Combinatorics
- Solved
- No attempts yet
Problem
You are given an array S of length N. Write a program that processes the following queries.
- u num : Replace Su with num. Then print the number of pairs (i, j) such that GCD(Si, Sj) > 1 and i < j. Here GCD(a, b) denotes the greatest common divisor of a and b.
Input
The first line contains the length of the array N (1 ≤ N ≤ 2 x 105) and the number of queries Q (1 ≤ Q ≤ 2 x 105), separated by a space.
The second line contains the integers Si (1 ≤ Si ≤ 106) representing the i-th element of the array (i = 0, 1, 2, ..., N-1), separated by spaces.
Each of the next Q lines contains a query given by the integers u (0 ≤ u ≤ N-1) and num (1 ≤ num ≤ 106), separated by a space.
Output
Print the answer to each query on its own line, in order.