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.

#include <iostream>
using namespace std;

int arr[200000];
int gcd(int a, int b){
	if(b == 0) return a;
	return gcd(b, a%b);
}
int main() {
	ios_base::sync_with_stdio(0);

Solution 2

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

Maintain an array, $\texttt{cnt}$, to store the count of divisors. For each value in the array, find its divisors and for each $u$ in those divisors, increment $\texttt{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$.

#include <iostream>
using namespace std;

int cnt[1000001]; //stores count of divisors
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n; cin >> n;
	for (int i = 0; i < n; i++){
		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

#include <bits/stdc++.h>
using namespace std;
 
int cnt[1000001];
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;