시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 121 37 24 32.000%

문제

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

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

입력

첫째 줄에 배열의 길이 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 ≤ uN-1), num(1 ≤ num ≤ 106)이 공백으로 구분되어 주어진다.

출력

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

예제 입력 1

4 1
2 2 2 3
0 3

예제 출력 1

2

출처

Contest > 네블컵 > 제2회 네블컵 G번