herdson   7달 전

Divide and Conquer 2.0

사슈카(Sashka)는 나눗셈 연산을 매우 좋아합니다. 그래서 그녀는 가을 정보학 대회를 위해 나눗셈과 관련된 문제를 하나 만들었습니다.

그녀가 가장 좋아하는 N개의 양의 정수로 이루어진 수열 a1​,a2​,…,aN​이 주어집니다. 그리고 총 Q개의 질문이 주어지는데, 각 질문 i는 세 개의 양의 정수 li​,ri​,di​로 구성됩니다.

질문의 내용: 수열의 li​번째부터 ri​번째 범위에 있는 숫자들 중, di​의 약수이거나 di​의 배수인 숫자의 개수를 구하세요.

입력

  • 첫 번째 줄: 수열의 크기 N과 질문의 개수 Q가 주어집니다.
  • 두 번째 줄: N개의 양의 정수 a1​,a2​,…,aN​이 주어집니다.
  • 세 번째 줄부터 Q개의 줄: 각 질문을 나타내는 li​,ri​,di​가 한 줄에 하나씩 주어집니다.

출력

  • 각 질문에 대한 답을 공백으로 구분하여 한 줄에 출력합니다.

제한 사항

  • 1≤N,Q≤100,000
  • 1≤ai​,di​≤200,000
  • 1≤li​≤ri​≤N
  • 수열 내의 모든 숫자는 서로 다릅니다 (ai​ != aj​).

댓글을 작성하려면 로그인해야 합니다.