GCD Queries Prefix Suffix
Hard
Computer Mathematics
GCD/LCM & Euclid
36 views
Problem Statement
Given array and q queries [l,r], output gcd of all except between l..r.
Input Format
n q then array then q lines l r.
Output Format
q lines gcd.
Example
5 2 2 6 9 3 15 2 3 4 4
1 3
Constraints
1
Input / Output Format
Input Format
n q then array then q lines l r.
Output Format
q lines gcd.
Constraints
1
Examples
Input:
5 2
2 6 9 3 15
2 3
4 4
Output:
1
3
Example Solution (Public)
Precompute prefixGcd and suffixGcd. Answer gcd(prefix[l-1], suffix[r+1]).
Official Solution Code
Precompute prefixGcd and suffixGcd. Answer gcd(prefix[l-1], suffix[r+1]).
Please login to submit solutions.