16154번 - 배열과 가희

문제

길이가 N인 배열 S가 주어진다. 다음 쿼리를 수행하는 프로그램을 작성하라.

• u num : S_u를 num으로 바꾼다. 그리고 GCD(S_i, S_j) > 1이면서 i < j인 쌍의 개수를 출력한다. 단, GCD(a, b)는 a와 b의 최대공약수를 나타낸다.

입력

첫째 줄에 배열의 길이 N(1 ≤ N ≤ 2 x 10⁵)과 쿼리의 개수 Q(1 ≤ Q ≤ 2 x 10⁵)가 공백으로 구분되어 주어진다.

둘째 줄에 배열의 i(i = 0, 1, 2, ..., N-1)번째 원소를 나타내는 정수 S_i(1 ≤ S_i ≤ 10⁶)가 공백으로 구분되어 주어진다.

셋째 줄부터 Q개의 각 줄에는 쿼리를 의미하는 정수 u(0 ≤ u ≤ N-1), num(1 ≤ num ≤ 10⁶)이 공백으로 구분되어 주어진다.

출력

Q개의 각 줄에 쿼리의 정답을 순서대로 한 줄에 하나씩 출력한다.

제한

힌트