등차수열과 쿼리

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

요약

첫째 항 a와 공차 d인 등차수열에서 구간 합 또는 구간의 최대공약수를 구하는 질의를 처리한다.

난이도: 보통10점 중 6점
유형: 수학, 정수론, 누적 합, 구현
정답자: 아직 제출이 없습니다

문제

등차수열은 연속하는 두 항의 차이가 일정한 수열을 뜻한다. 연속한 두 항 중 뒷항에서 앞항을 뺀 값을 공차라고 한다. 초항이 $a$ 이고 공차가 $d$ 인 등차수열이 주어진다. 수열의 $i$ 번째 원소를 $A_i$ 라 할 때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

1 l r : $A_l, A_{l+1}, ... , A_r$ 의 합을 출력한다.
2 l r : $A_l, A_{l+1}, ... , A_r$ 의 최대공약수를 출력한다. 이는 $A_l, A_{l+1}, ... , A_r$ 의 공통된 약수 중 가장 큰 양의 정수를 뜻한다.

입력

첫째 줄에 수열의 초항 $a$ 와 공차 $d$ 가 주어진다.

둘째 줄에는 쿼리의 개수 $q$ 가 주어진다.

셋째 줄부터 $q$ 개의 줄에는 쿼리가 한 줄에 하나씩 주어진다.

출력

각각의 쿼리마다 정답을 한 줄에 하나씩 출력한다.

제한

$1 ≤ a ≤ 10^6$ , $0 ≤ d ≤ 10^6$
$1 ≤ q ≤ 10^6$
$1 ≤ l ≤ r ≤ 10^6$

예제2

예제 1
입력
```
4 2
3
1 1 1
1 1 2
2 1 2
```
예상 출력
```
4
10
2
```
예제 2
입력
```
5 3
2
1 2 5
2 3 6
```
예상 출력
```
50
1
```