시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 142 36 28 31.461%

문제

창영이가 에러를 찾기 위해서 디버깅을 하고 있다. 이 프로그램은 크기가 N이고 0으로 채워져있는 배열을 a를 만들고, 아래 something 함수를 호출한다.

void something(int jump) {
    int i = 0;
    while (i < N) {
        a[i] = a[i] + 1;
        i = i + jump;
    }
}

창영이는 함수를 K번 호출하려고 한다. 각각 호출할 때, 인자로 넘기는 jump의 값은 X1, X2, X3, ... Xk 순서이다.

이렇게 호출한 뒤에는 배열의 값이 정상적으로 들어갔는지를 확인하려고 한다. 확인은 총 Q번 하고, 매번 확인을 할 때마다 L과 R(L ≤ R)을 정한뒤, 그 구간의 배열의 합을 구한다. 즉, a[L] + a[L+1] + ... + a[R]을 구한다.

함수를 호출할 때 필요한 X의 값과 창영이가 확인한 횟수 Q가 주어졌을 때, 확인한 결과(배열의 합)을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 배열의 크기 N과 함수의 호출 횟수 K가 주어진다. (1 ≤ N, K ≤ 106)

둘째 줄에 함수를 호출할 때 사용하는 인자의 값 X1, X2..., Xk가 공백으로 구분되어 주어진다. (1 ≤ Xi < N)

셋째 줄에는 확인하는 횟수 Q가 주어진다. (1 ≤ Q ≤ 106)

넷째 줄부터 Q개 줄에는 각 확인에 사용하는 L과 R이 주어진다. (0 ≤ L ≤ R < N)

출력

출력은 총 Q줄이다. 창영이가 확인하는데 사용한 L과 R이 주어졌을 때, a[L] + a[L+1] + a[L+2] ... + a[R]을 출력한다. 

예제 입력

10 4
1 1 2 1
3
0 9
2 6
7 7

예제 출력

35
18
3

힌트

출처

Contest > Croatian Open Competition in Informatics > COCI 2009/2010 > Contest #5 5번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: khsoo01