배열과 가희

시간 제한2초메모리 제한512 MB

요약

배열의 값을 갱신한 뒤 두 값의 최대공약수가 1보다 큰 쌍의 개수를 구합니다.

문제

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

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

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

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

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

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