GCD Queries


Submit solution

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

Authors:
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 (ij), 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 (1N105). Following this line is N space separated integers (2109ai2109 where ai denotes the ith integer).

The next line contains a single integer Q (1Q105) 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: ij and 0i,j<N
  • 2 i x
    • Update A[i] to the value x, i.e. set A[i]=x
    • Constraints: 2109x2109 and 0i<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

Copy
5
21 21 21 21 21
4
1 0 4
2 0 14
2 2 7
1 0 2

Example output

Copy
21
7

Notes

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


Comments


  • 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!