시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB71223918333.455%

문제

창영이가 에러를 찾기 위해서 디버깅을 하고 있다. 이 프로그램은 크기가 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]을 출력한다. 

예제 입력 1

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

예제 출력 1

35
18
3

예제 입력 2

11 3
3 7 10
3
0 10
2 6
7 7

예제 출력 2

8
2
1

예제 입력 3

1000000 6
12 3 21 436 2 19
2
12 16124
692 29021

예제 출력 3

16422
28874
W3sicHJvYmxlbV9pZCI6IjI5MDAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YTgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Y2MzZFx1YzYwMVx1Yzc3NFx1YWMwMCZuYnNwO1x1YzVkMFx1YjdlY1x1Yjk3YyBcdWNjM2VcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YjUxNFx1YmM4NFx1YWU0NVx1Yzc0NCBcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQwIFx1ZDA2Y1x1YWUzMFx1YWMwMCBOXHVjNzc0XHVhY2UwIDBcdWM3M2NcdWI4NWMgXHVjYzQ0XHVjNmNjXHVjODM4XHVjNzg4XHViMjk0IFx1YmMzMFx1YzVmNFx1Yzc0NCBhXHViOTdjIFx1YjljY1x1YjRlNFx1YWNlMCwgXHVjNTQ0XHViNzk4IHNvbWV0aGluZyBcdWQ1NjhcdWMyMThcdWI5N2MgXHVkNjM4XHVjZDljXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG52b2lkIHNvbWV0aGluZyhpbnQganVtcCkge1xyXG4gICAgaW50IGkgPSAwO1xyXG4gICAgd2hpbGUgKGkgJmx0OyBOKSB7XHJcbiAgICAgICAgYVtpXSA9IGFbaV0gKyAxO1xyXG4gICAgICAgIGkgPSBpICsganVtcDtcclxuICAgIH1cclxufTxcL3ByZT5cclxuXHJcbjxwPlx1Y2MzZFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWQ1NjhcdWMyMThcdWI5N2MgS1x1YmM4OCBcdWQ2MzhcdWNkOWNcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWFjMDFcdWFjMDEgXHVkNjM4XHVjZDljXHVkNTYwIFx1YjU0YywgXHVjNzc4XHVjNzkwXHViODVjIFx1YjExOFx1YWUzMFx1YjI5NCBqdW1wXHVjNzU4IFx1YWMxMlx1Yzc0MCBYPHN1Yj4xPFwvc3ViPiwgWDxzdWI+MjxcL3N1Yj4sIFg8c3ViPjM8XC9zdWI+LCAuLi4gWDxzdWI+azxcL3N1Yj4gXHVjMjFjXHVjMTFjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWI4MDdcdWFjOGMgXHVkNjM4XHVjZDljXHVkNTVjIFx1YjRhNFx1YzVkMFx1YjI5NCBcdWJjMzBcdWM1ZjRcdWM3NTggXHVhYzEyXHVjNzc0IFx1YzgxNVx1YzBjMVx1YzgwMVx1YzczY1x1Yjg1YyBcdWI0ZTRcdWM1YjRcdWFjMTRcdWIyOTRcdWM5YzBcdWI5N2MgXHVkNjU1XHVjNzc4XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVkNjU1XHVjNzc4XHVjNzQwIFx1Y2QxZCBRXHViYzg4IFx1ZDU1OFx1YWNlMCwgXHViOWU0XHViYzg4IFx1ZDY1NVx1Yzc3OFx1Yzc0NCBcdWQ1NjAgXHViNTRjXHViOWM4XHViMmU0IExcdWFjZmMgUihMICZsZTsgUilcdWM3NDQgXHVjODE1XHVkNTVjXHViNGE0LCBcdWFkZjggXHVhZDZjXHVhYzA0XHVjNzU4IFx1YmMzMFx1YzVmNFx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVhZDZjXHVkNTVjXHViMmU0LiBcdWM5ODksIGFbTF0gKyBhW0wrMV0gKyAuLi4gKyBhW1JdXHVjNzQ0IFx1YWQ2Y1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTY4XHVjMjE4XHViOTdjIFx1ZDYzOFx1Y2Q5Y1x1ZDU2MCBcdWI1NGMgXHVkNTQ0XHVjNjk0XHVkNTVjIFhcdWM3NTggXHVhYzEyXHVhY2ZjIFx1Y2MzZFx1YzYwMVx1Yzc3NFx1YWMwMCBcdWQ2NTVcdWM3NzhcdWQ1NWMgXHVkNjlmXHVjMjE4IFFcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVkNjU1XHVjNzc4XHVkNTVjIFx1YWNiMFx1YWNmYyhcdWJjMzBcdWM1ZjRcdWM3NTggXHVkNTY5KVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYzMwXHVjNWY0XHVjNzU4IFx1ZDA2Y1x1YWUzMCBOXHVhY2ZjIFx1ZDU2OFx1YzIxOFx1Yzc1OCBcdWQ2MzhcdWNkOWMgXHVkNjlmXHVjMjE4IEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4sIEsgJmxlOyAxMDxzdXA+NjxcL3N1cD4pPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkNTY4XHVjMjE4XHViOTdjIFx1ZDYzOFx1Y2Q5Y1x1ZDU2MCBcdWI1NGMgXHVjMGFjXHVjNmE5XHVkNTU4XHViMjk0IFx1Yzc3OFx1Yzc5MFx1Yzc1OCBcdWFjMTIgWDxzdWI+MTxcL3N1Yj4sIFg8c3ViPjI8XC9zdWI+Li4uLCBYPHN1Yj5rPFwvc3ViPlx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBYPHN1Yj5pPFwvc3ViPiAmbHQ7IE4pPFwvcD5cclxuXHJcbjxwPlx1YzE0Ylx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNjU1XHVjNzc4XHVkNTU4XHViMjk0IFx1ZDY5Zlx1YzIxOCBRXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBRICZsZTsgMTA8c3VwPjY8XC9zdXA+KTxcL3A+XHJcblxyXG48cD5cdWIxMzdcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIFFcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWQ2NTVcdWM3NzhcdWM1ZDAgXHVjMGFjXHVjNmE5XHVkNTU4XHViMjk0IExcdWFjZmMgUlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgwICZsZTsgTCAmbGU7IFIgJmx0OyBOKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2Q5Y1x1YjgyNVx1Yzc0MCBcdWNkMWQgUVx1YzkwNFx1Yzc3NFx1YjJlNC4gXHVjYzNkXHVjNjAxXHVjNzc0XHVhYzAwIFx1ZDY1NVx1Yzc3OFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWMwYWNcdWM2YTlcdWQ1NWMgTFx1YWNmYyBSXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIGFbTF0gKyBhW0wrMV0gKyBhW0wrMl0gLi4uICsgYVtSXVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjkwMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBST0dSQU0iLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIGlzIHRyeWluZyB0byBkZWJ1ZyBhIHBpZWNlIG9mIGhpcyBjb2RlLiBGaXJzdCBoZSBjcmVhdGVzIGFuIGFycmF5IG9mIE4gaW50ZWdlcnMgYW5kIGZpbGxzIGl0IHdpdGggemVyb3MuIFRoZW4gaGUgcmVwZWF0ZWRseSBjYWxscyB0aGUgZm9sbG93aW5nIHByb2NlZHVyZSAoaGUgaXMgc3VjaCBhIGdvb2QgY29kZXIgaGUgY29kZWQgaXQgaW4gYm90aCBDKysgYW5kIFBhc2NhbCk6PFwvcD5cclxuXHJcbjxwcmU+XHJcbnZvaWQgc29tZXRoaW5nKGludCBqdW1wKSB7XHJcbiAgICBpbnQgaSA9IDA7XHJcbiAgICB3aGlsZSAoaSAmbHQ7IE4pIHtcclxuICAgICAgICBhW2ldID0gYVtpXSArIDE7XHJcbiAgICAgICAgaSA9IGkgKyBqdW1wO1xyXG4gICAgfVxyXG59PFwvcHJlPlxyXG5cclxuPHA+QXMgeW91IGNhbiBzZWUsIHRoaXMgcHJvY2VkdXJlIGluY3JlYXNlcyBieSBvbmUgYWxsIGVsZW1lbnRzIGluIHRoZSBhcnJheSB3aG9zZSBpbmRpY2VzIGFyZSBkaXZpc2libGUgYnkganVtcC48XC9wPlxyXG5cclxuPHA+TWlya28gY2FsbHMgdGhlIHByb2NlZHVyZSBleGFjdGx5IEsgdGltZXMsIHVzaW5nIHRoZSBzZXF1ZW5jZSBYPHN1Yj4xPFwvc3ViPiBYPHN1Yj4yPFwvc3ViPiBYPHN1Yj4zPFwvc3ViPi4uLiBYPHN1Yj5rPFwvc3ViPiBhcyBhcmd1bWVudHMuPFwvcD5cclxuXHJcbjxwPkFmdGVyIHRoaXMsIE1pcmtvIGhhcyBhIGxpc3Qgb2YgUSBzcGVjaWFsIHBhcnRzIG9mIHRoZSBhcnJheSBoZSBuZWVkcyB0byBjaGVjayB0byB2ZXJpZnkgdGhhdCBoaXMgY29kZSBpcyB3b3JraW5nIGFzIGl0IHNob3VsZCBiZS4gRWFjaCBvZiB0aGlzIHBhcnRzIGlzIGRlZmluZWQgYnkgdHdvIG51bWJlcnMsIEwgYW5kIFIgKEwgJmxlOyBSKSB0aGUgbGVmdCBhbmQgcmlnaHQgYm91bmQgb2YgdGhlIHNwZWNpYWwgcGFydC4gVG8gY2hlY2sgdGhlIGNvZGUsIE1pcmtvIG11c3QgY29tcHV0ZSB0aGUgc3VtIG9mIGFsbCBlbGVtZW50cyBvZiBzZXEgYmV0d2VlbiBhbmQgaW5jbHVkaW5nIEwgYW5kIFIuIEluIG90aGVyIHdvcmRzIHNlcVtMXSArIHNlcVtMKzFdICsgc2VxW0wrMl0gKyAuLi4gKyBzZXFbUl0uIFNpbmNlIGhlIG5lZWRzIHRvIGtub3cgdGhlIGFuc3dlciBpbiBhZHZhbmNlIGluIG9yZGVyIHRvIGNoZWNrIGl0LCBoZSBhc2tlZCB5b3UgdG8gaGVscCBoaW0uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gaW50ZWdlcnMsIE4gKDEgJmxlOyBOICZsZTsgMTA8c3VwPjY8XC9zdXA+KSwgc2l6ZSBvZiB0aGUgYXJyYXksIGFuZCBLICgxICZsZTsgSyAmbGU7IDEwPHN1cD42PFwvc3VwPiksIG51bWJlciBvZiBjYWxscyB0byBzb21ldGhpbmcgTWlya28gbWFrZXMuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyBLIGludGVnZXJzOiBYPHN1Yj4xPFwvc3ViPlg8c3ViPjI8XC9zdWI+WDxzdWI+MzxcL3N1Yj4gLi4uIFg8c3ViPms8XC9zdWI+LCBhcmd1bWVudHMgcGFzc2VkIHRvIHRoZSBwcm9jZWR1cmUuICgxICZsZTsgWDxzdWI+aTxcL3N1Yj4gJmx0OyBOKS48XC9wPlxyXG5cclxuPHA+TmV4dCBsaW5lIGNvbnRhaW5zIG9uZSBpbnRlZ2VyIFEgKDEgJmxlOyBRICZsZTsgMTA8c3VwPjY8XC9zdXA+KSwgbnVtYmVyIG9mIHNwZWNpYWwgcGFydHMgb2YgdGhlIGFycmF5IE1pcmtvIG5lZWRzIHRvIGNoZWNrLjxcL3A+XHJcblxyXG48cD5OZXh0IFEgbGluZXMgY29udGFpbiB0d28gaW50ZWdlcnMgZWFjaCBMPHN1Yj5pPFwvc3ViPiBhbmQgUjxzdWI+aTxcL3N1Yj4oMCAmbGU7IEw8c3ViPmk8XC9zdWI+JmxlOyBSPHN1Yj5pPFwvc3ViPiAmbHQ7IE4pLCBib3VuZHMgb2YgZWFjaCBzcGVjaWFsIHBhcnQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG91dHB1dCBzaG91bGQgY29udGFpbiBleGFjdGx5IFEgbGluZXMuIFRoZSBpPHN1cD50aDxcL3N1cD4gbGluZSBzaG91bGQgY29udGFpbiB0aGUgc3VtIG9mIGVsZW1lbnRzIHNlcVtMPHN1Yj5pPFwvc3ViPl0gKyBzZXFbTDxzdWI+aTxcL3N1Yj4rMV0gKyBzZXFbTDxzdWI+aTxcL3N1Yj4rMl0gKyAuLi4gKyBzZXFbUjxzdWI+aTxcL3N1Yj5dLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

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

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