CSES - Common Divisor

Authors: Andrew Wang, Andi Qu

Edit This Page

Solution 1

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 around half of the test cases.

Implementation

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

C++

#include <iostream>
using namespace std;


const int MAX_N = 2e5;


int arr[MAX_N];


int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }


int main() {

Java

import java.io.*;
import java.util.*;


public class CommonDivisors {
	public static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }


	public static void main(String[] args)
	    throws NumberFormatException, IOException {
		BufferedReader io =
		    new BufferedReader(new InputStreamReader(System.in));

Python

from math import gcd


n = int(input())


arr = list(map(int, input().split()))


ans = 1
for i in range(n - 1):
	for j in range(i + 1, n):
		ans = max(ans, gcd(arr[i], arr[j]))


print(ans)

Solution 2

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

Implementation

Time Complexity: O(Nmax⁡(xi))\mathcal{O}(N\sqrt{\max(x_i)})

C++

#include <cmath>
#include <iostream>
using namespace std;


const int MAX_VAL = 1e6;


// divisors[i] = stores the count of numbers that have i as a divisor
int divisors[MAX_VAL + 1];


int main() {

Java

Warning!

Due to the tight time limit, the following Java solution still receives TLE on a few of the test cases.

import java.io.*;
import java.util.*;


public class CommonDivisors {
	public static final int MAX_VAL = 1000000;


	// divisors[i] = stores the count of numbers that have i as a divisor
	public static int[] divisors = new int[MAX_VAL + 1];


	public static void main(String[] args)

Python

Warning!

Due to the tight time limit, the following Python solution still receives TLE on about half the test cases.

from math import sqrt


MAX_VAL = 1000000
divisors = [0] * (MAX_VAL + 1)


n = int(input())
a = list(map(int, input().split()))
for i in range(n):
	up = int(sqrt(a[i]))
	for div in range(1, up + 1):

Solution 3

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

∑i=1max⁡(xi)max⁡(xi)/i≈max⁡(xi)log⁡(max⁡(xi)).\sum_{i = 1}^{\max(x_i)} \max(x_i)/i \approx \max(x_i)\log(\max(x_i)).

Implementation

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

C++

#include <bits/stdc++.h>
using namespace std;


const int MAX_VAL = 1e6;


// occ_num[i] contains the number of times i occurs in the array
vector<int> occ_num(MAX_VAL + 1);


int main() {
	ios_base::sync_with_stdio(0);

Java

import java.io.*;
import java.util.*;


public class CommonDivisors {
	public static final int MAXX = 1000000;


	public static void main(String[] args)
	    throws NumberFormatException, IOException {
		BufferedReader io =
		    new BufferedReader(new InputStreamReader(System.in));

Python

MAXX = int(1e6 + 5)
n = int(input())
arr = list(map(int, input().split()))
p = [0] * MAXX


for i in range(n):
	p[arr[i]] += 1


for i in range(MAXX, 0, -1):
	div = 0
	for j in range(i, MAXX, i):
		div += p[j]
	if div >= 2:
		print(i)
		break

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum