아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

구간 최대공약수

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

요약
배열에 구간 덧셈과 구간 최대공약수 질의를 처리한다. 차분 배열의 최대공약수와 한 점의 값을 함께 관리한다.
난이도

어려움10점 중 8점

유형
세그먼트 트리, 정수론, 수학
정답자
아직 제출이 없습니다

문제

자연수 NN개로 이루어진 수열 A1,A2,…,ANA_1, A_2, \dots, A_N이 있다. 이 수열에 다음 두 가지 연산을 수행한다.

  • 연속한 구간의 모든 원소에 같은 값을 더한다.
  • 연속한 구간에 있는 원소의 최대공약수를 구한다.

연산을 입력에 주어진 순서대로 처리하고, 최대공약수를 구하는 연산마다 답을 출력하라.

입력

첫째 줄에 수열의 원소 개수 NN이 주어진다. (1≤N≤1000001 \le N \le 100000)

둘째 줄에 수열의 원소 NN개가 공백으로 구분되어 주어진다. ii번째 수가 AiA_i이고, 1≤Ai≤1091 \le A_i \le 10^9이다.

셋째 줄에 연산의 개수 QQ가 주어진다. (1≤Q≤1000001 \le Q \le 100000)

이어지는 QQ개의 줄에 연산이 한 줄에 하나씩 주어진다. 각 줄은 세 정수 TT, AA, BB로 이루어진다.

  • TT가 0이 아니면 AA번째 원소부터 BB번째 원소까지 모든 원소에 TT를 더한다.
  • TT가 0이면 AA번째 원소부터 BB번째 원소까지의 최대공약수를 출력해야 한다.

TT는 0≤T≤1090 \le T \le 10^9이고, AA와 BB는 1≤A≤B≤N1 \le A \le B \le N을 만족한다. TT가 0인 연산은 하나 이상 주어진다.

출력

TT가 0인 연산마다 그 구간의 최대공약수를 입력에 주어진 순서대로 한 줄에 하나씩 출력한다.

예제8

  1. 예제 1

    입력
    4
6 3 38 49
5
0 1 3
9 2 2
0 1 2
6 3 3
0 3 4
    예상 출력
    1
6
1

  2. 예제 2

    입력
    1
1000000000
3
0 1 1
1000000000 1 1
0 1 1
    예상 출력
    1000000000
2000000000

  3. 예제 3

    입력
    5
12 12 12 12 12
5
0 1 5
12 1 2
0 1 5
0 1 2
0 3 5
    예상 출력
    12
12
24
12

  4. 예제 4

    입력
    8
6 12 18 24 30 36 42 48
6
0 1 8
0 2 4
6 1 8
0 1 8
1000000000 4 8
0 4 5
    예상 출력
    6
6
6
2

  5. 예제 5

    입력
    4
1000000000 1000000000 1000000000 999999999
6
0 1 4
0 1 3
1000000000 1 4
0 1 3
0 4 4
0 1 4
    예상 출력
    1
1000000000
2000000000
1999999999
1

  6. 예제 6

    입력
    10
1 2 4 8 16 32 64 128 256 512
8
0 1 10
0 2 4
0 5 10
3 1 1
0 1 3
0 9 10
512 1 10
0 1 10
    예상 출력
    1
2
16
2
256
2

  7. 예제 7

    입력
    5
100 200 300 400 500
6
0 1 5
0 1 1
0 2 3
0 3 5
0 5 5
0 2 5
    예상 출력
    100
100
100
100
500
100

  8. 예제 8

    입력
    3
5 5 5
5
5 3 3
0 1 3
0 3 3
7 1 3
0 1 3
    예상 출력
    5
10
1