Skip to main content

Oracle

Oracle OA-7 2023

Problem Description

A renowned mathematician, Anna Taylor, was known for her significant contributions to number theory, particularly in the study of prime numbers and divisibility. One of the essential tools in number theory is the Greatest Common Divisor (GCD), which has numerous applications, including in algorithms related to cryptography.

For the multiset of positive integers (a = (a_1, a_2, ..., a_k)), let the GCD of (a) be defined as (x), where (x) is the maximum positive integer such that all the integers in the multiset (a) are divisible by (x).

Given a sequence of (n) integers arr, find the subarray of length greater than 1 whose GCD is the maximum possible. If there exist multiple subarrays, then choose the largest in length.

Output the maximum possible GCD and the corresponding maximum possible length of this GCD.

Input Format

int arr[n]: an array of integers.

Output Format

int[]: the maximum possible GCD and the corresponding maximum possible length of this GCD.

Constraints:

  • 1 ≤ n ≤ 10^5
  • 1 ≤ arr[i] ≤ 10^9