GCD Queries

Submit solution

Points: 1
Time limit: 2.0s
Memory limit: 512M

Problem type

The Greatest Common Divisor (GCD) of two integers, \(a\) and \(b\), is the largest number which divides both \(a\) and \(b\). For example: \(GCD(10, 5) = 5\), \(GCD(21, 14) = 7\). Let us assume \(GCD(0, 0) = 0\).

You are given an array, \(A\), of \(N\) integers. You are tasked to answer \(Q\) queries. There are two types of queries:

  1. print the GCD of the integers in \(A\) from index \(i\) to index \(j\) (\(i \leq j\)), i.e. \(GCD(A[i..j])\), where \(i\) and \(j\) are inclusive.
  2. update any element within the array to a specified value

Input specification

The first line of input contains the integer \(N\) (\(1 \leq N \leq 10^5\)). Following this line is \(N\) space separated integers (\(-2*10^9 \leq a_i \leq 2*10^9\) where \(a_i\) denotes the \(i^{\text{th}}\) integer).

The next line contains a single integer \(Q\) (\(1 \leq Q \leq 10^5\)) describing the number of queries to answer. Then \(Q\) lines follow, each of these lines are may be of the form:

  • 1 i j
    • Print the Greatest Common Divisor of the integers in \(A\) from index \(i\) to index \(j\)
    • Constraints: \(i \leq j\) and \(0 \leq i, j < N\)
  • 2 i x
    • Update \(A[i]\) to the value \(x\), i.e. set \(A[i] = x\)
    • Constraints: \(-2*10^9 \leq x \leq 2*10^9\) and \(0 \leq i < N\)

Output specification

For each query which begins with \(1\), please print the Greatest Common Divisor of the integers in A from index \(i\) to index \(j\).

Example input

21 21 21 21 21
1 0 4
2 0 14
2 2 7
1 0 2

Example output



This problem has a lot of input and output. Please use fast input and output methods. Some tips are given here.


  • 1
    max  commented on Nov. 10, 2018, 3:29 a.m.

    No judge available

    I am getting a message saying, "No judge is available for this problem" when I go to submit my solution.

    Edit: All fixed now! Thanks!