Algorithm
Problem Name: beecrowd | 3306
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/3306
Search and Change
By Abner Samuel P. Palmeira, Instituto Federal do Sul de Minas Gerais 
Brazil
Timelimit: 1
Given a vector with N elements, answer Q queries of types:
1 A B V: Add V across all elements from position A to position B of the vector.
2 A B: Returns the Greatest Common Divisor of all elements from positions A to B in the vector
Input
The input consists of several test cases. The first line of each test case contains two integers N Q, representing respectively the vector size and the number of queries. The second line of input contains N integers representing the elements of the vector. The next Q lines contain the queries as described above.
Limits:
1 ≤ N; Q ≤ 105
Output
For each type 2 query print the GCD of all vector positions that are in the AB range
| Input Samples | Output Samples |
|
7 4 1 8 4 16 6 13 20 2 2 4 2 5 7 1 5 7 1 2 5 7 |
4 1 7 |
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const { readFileSync } = require("node:fs")
const input = readFileSync("/dev/stdin", "utf8")
.trimEnd() // Prevent EOF
.split(/\s+/g)
.map(value => Number.parseInt(value, 10))
//// MATH ////
const MyMath = Object.create(Math, {
gcd: {
/**
* @param {number} x
* @param {number} y
*/
value: function gcd(x, y) {
if (isNaN(x) || isNaN(y)) return Number.NaN
x = Math.abs(x)
y = Math.abs(y)
while (y) [x, y] = [y, x % y]
return x
},
configurable: false,
enumerable: false,
writable: false
}
})
// //// MAIN ////
async function main() {
const output = []
while (input.length > 0) {
const [N, Q] = input.splice(0, 2)
const elements = input.splice(0, N)
for (let q = 1; q < = Q; q += 1) {
const [C, A, B] = input.splice(0, 3)
if (C == 1) {
const V = input.shift()
for (let index = A - 1; index < B; index += 1)
elements[index] += V
} else if (C == 2) {
let gcd = elements[A - 1]
for (let index = A; index < B; index += 1)
gcd = MyMath.gcd(gcd, elements[index])
output.push(gcd)
} else { output.push(q) }
}
}
console.log(output.join("\n"))
}
main()
Input
Output