GCD Queries Prefix Suffix
Computer Mathematics
Hard
2 views
Problem Description
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.
Sample Test Case
Input:
5 2
2 6 9 3 15
2 3
4 4
Official Solution
Precompute prefixGcd and suffixGcd. Answer gcd(prefix[l-1], suffix[r+1]).
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!