CSES - Common Divisor

Solution 1

Time Complexity: $\mathcal{O}(N^2\log (\max (x_i)))$

The naive approach would be to brute-force each pair of numbers in the array and calculate the maximum GCD. Sadly, this solution gets TLE on half of the test cases.

1#include <iostream>
2using namespace std;
3
4int arr[200000];
5int gcd(int a, int b){
6    if(b == 0) return a;
7    return gcd(b, a%b);
8}
9int main() {
10    ios_base::sync_with_stdio(0);

Solution 2

Time Complexity: $\mathcal{O}(N\sqrt{\max (x_i)})$

Maintain an array, $\text{cnt}$, to store the count of divisors. For each value in the array, find its divisors and for each $u$ in those divisors, increment $\text{cnt}$ by one. The greatest GCD shared by two elements in the array will be the greatest index in our stored count for divisors with a count greater than or equal to $2$.

1#include <iostream>
2using namespace std;
3
4int cnt[1000001]; //stores count of divisors
5int main() {
6    ios_base::sync_with_stdio(0);
7    cin.tie(0);
8    int n; cin >> n;
9    for (int i = 0; i < n; i++){
10        int a; cin >> a;

Solution 3

Time Complexity: $\mathcal{O}(\max (x_i)\log (\max (x_i)))$

Given a value, $x$, we can check whether a pair has a GCD equal to $x$ by checking all the multiples of $x$. With that information, loop through all possible values of $x$ and check if it is a divisor to two or more values. This works in $\mathcal{O}(\max (x_i)\log (\max (x_i)))$ since

1#include <bits/stdc++.h>
2using namespace std;
3 
4int cnt[1000001];
5 
6int main() {
7    ios_base::sync_with_stdio(0);
8    cin.tie(0);
9    int n;
10    cin >> n;