Ghd (Codeforces 364D)
Tags: Math, probabilities

John Doe offered his sister Jane Doe find the gcd of some set of numbers a.Gcd is a positive integer g, such that all number from the set are evenly divisible by g and there isn't such g' (g' > g), that all numbers of the set are evenly divisible by g'.Unfortunately Jane couldn't cope with the task and John offered her to find the ghd of the same subset of numbers.Ghd is a positive integer g, such that at least half of numbers from the set are evenly divisible by g and there isn't such g' (g' > g) that at least half of the numbers from the set are evenly divisible by g'.Jane coped with the task for two hours. Please try it, too.

Input: The first line contains an integer n (1 ≤ n ≤ 106) showing how many numbers are in set a. The second line contains space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 1012). Please note, that given set can contain equal numbers.Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the %I64d specifier.

Output: Print a single integer g — the Ghd of set a.


Sample Inputs:
6
6 2 3 4 5 6

5
5 5 6 10 15

Sample Outputs:
3

5

Solution (Python):
import sys
import heapq
from heapq import *
from math import log2, ceil, floor, gcd, sqrt, log, perm, comb, factorial
from random import randrange
from bisect import bisect_left
from collections import defaultdict, Counter, deque, OrderedDict
from functools import lru_cache, reduce
from bisect import bisect_left, bisect_right
from types import GeneratorType
input = lambda : sys.stdin.buffer.readline().decode().rstrip()

class dict_(dict):
    RANDOM = randrange(2 ** 62)

    def __init__(self, dd):
        super().__init__({k ^ self.RANDOM: v for (k, v) in dd.items()})

    def __missing__(self, key):
        return 0

    def __setitem__(self, key, value):
        super().__setitem__(key ^ self.RANDOM, value)

    def __getitem__(self, item):
        return super().__getitem__(item ^ self.RANDOM)

    def __contains__(self, item):
        return super().__contains__(item ^ self.RANDOM)

    def items(self):
        for (k, v) in super().items():
            yield (k ^ self.RANDOM, v)

    def keys(self):
        for k in super().keys():
            yield (k ^ self.RANDOM)

    def __repr__(self):
        return '{0}'.format({k ^ self.RANDOM: v for (k, v) in super().items()})

def add_edge(node1, node2, graph):
    if node1 not in graph:
        graph[node1] = []
    if node2 not in graph:
        graph[node2] = []
    graph[node1].append(node2)
    graph[node2].append(node1)

class disjointset:

    def __init__(self, n):
        (self.rank, self.parent) = (array('i', [0] * (n + 1)), array('i', [i for i in range(n + 1)]))
        (self.n, self.even) = (n, array('b', [0] * (n + 1)))

    def find(self, x):
        xcopy = x
        while x != self.parent[x]:
            x = self.parent[x]
        while xcopy != x:
            (self.parent[xcopy], xcopy) = (x, self.parent[xcopy])
        return x

    def union(self, x, y):
        (xpar, ypar) = (self.find(x), self.find(y))
        if xpar == ypar:
            return 1
        (par, child) = (xpar, ypar)
        if self.rank[xpar] < self.rank[ypar]:
            (par, child) = (ypar, xpar)
        elif self.rank[xpar] == self.rank[ypar]:
            self.rank[xpar] += 1
        self.parent[child] = par
        self.even[par] |= self.even[child]
        self.n -= 1
        return 0

def dijkstra(graph, start1):
    distances = {node: float('inf') for node in graph}
    distances[start1] = 0
    heap = [(0, start1, [start1])]
    paths = [-1 for i in range(n + 1)]
    while heap:
        (current_distance, current_node, path) = heapq.heappop(heap)
        if current_distance > distances[current_node]:
            continue
        for (neighbor, weight) in graph[current_node]:
            distance = current_distance + weight
            if distance < distances[neighbor]:
                lst = path
                lst.append(neighbor)
                paths[neighbor] = current_node
                distances[neighbor] = distance
                heapq.heappush(heap, (distance, neighbor, lst))
    return (distances, paths)

def mergeSort(arr, n):
    temp_arr = [0] * n
    return _mergeSort(arr, temp_arr, 0, n - 1)

def _mergeSort(arr, temp_arr, left, right):
    inv_count = 0
    if left < right:
        mid = (left + right) // 2
        inv_count += _mergeSort(arr, temp_arr, left, mid)
        inv_count += _mergeSort(arr, temp_arr, mid + 1, right)
        inv_count += merge(arr, temp_arr, left, mid, right)
    return inv_count

def merge(arr, temp_arr, left, mid, right):
    i = left
    j = mid + 1
    k = left
    inv_count = 0
    while i <= mid and j <= right:
        if arr[i] <= arr[j]:
            temp_arr[k] = arr[i]
            k += 1
            i += 1
        else:
            temp_arr[k] = arr[j]
            inv_count += mid - i + 1
            k += 1
            j += 1
    while i <= mid:
        temp_arr[k] = arr[i]
        k += 1
        i += 1
    while j <= right:
        temp_arr[k] = arr[j]
        k += 1
        j += 1
    for loop_var in range(left, right + 1):
        arr[loop_var] = temp_arr[loop_var]
    return inv_count

def Divisors(n):
    divisors = {}
    for num in [n]:
        lst = set()
        i = 1
        while i <= sqrt(num):
            if num % i == 0:
                if num / i == i:
                    lst.add(i)
                else:
                    lst.update([i, num // i])
            i = i + 1
        divisors[num] = list(lst)
    return divisors[num]

def binpow(a, b):
    if b == 0:
        return 1
    res = binpow(a, b // 2)
    res = pow(res, 2, MOD)
    if b % 2:
        return res * a % MOD
    return res

def mod_inverse(a):
    return binpow(a, MOD - 2)

def factors(n):
    if n == 0:
        return set()
    return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def inverse_mod(num):
    a = mod - 2
    result = 1
    result = pow(num, a, mod)
    return result

def mex(arr, N):
    arr1 = arr.copy()
    arr1.sort()
    mex = 0
    for idx in range(N):
        if arr1[idx] == mex:
            mex += 1
    return mex

def mergeDictionary(dict_1, dict_2):
    dict_3 = {**dict_1, **dict_2}
    for (key, value) in dict_3.items():
        if key in dict_1 and key in dict_2:
            dict_3[key] = value + dict_1[key]
    return dict_3

def rindex(lst, value):
    lst.reverse()
    i = lst.index(value)
    lst.reverse()
    return len(lst) - i - 1

def prefix_sum(arr, length_arr, prefix_sum):
    prefix_sum[0] = arr[0]
    for i in range(1, length_arr):
        prefix_sum[i] = prefix_sum[i - 1] + arr[i]

def suffix_sum(arr, length_arr, suffix_sum):
    suffix_sum[length_arr - 1] = arr[length_arr - 1]
    for i in reversed(range(length_arr - 1)):
        suffix_sum[i] = suffix_sum[i + 1] + arr[i]
letters = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']

def bootstrap(f):
    stack = []

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc
mod = 10 ** 9 + 7
import random

def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    random.seed(12312 ^ 42)
    random.shuffle(arr)
    c = Counter(arr)
    half = (n + 1) // 2
    ans = 1
    used = set()
    for x in range(min(n, 6)):
        ar = arr[x]
        if ar in used:
            continue
        used.add(ar)
        g = {}
        for ai in c.keys():
            try:
                g[gcd(ai, ar)] += c[ai]
            except:
                g[gcd(ai, ar)] = c[ai]
        for d in Divisors(ar):
            if d > ans:
                cur = 0
                for (k, v) in g.items():
                    if k % d == 0:
                        cur += v
                        if cur >= half:
                            ans = max(ans, d)
    print(ans)
solve()

Solution (Python):
if True:
    from io import BytesIO, IOBase
    import math
    import random
    import sys
    import os
    import bisect
    import typing
    from collections import Counter, defaultdict, deque
    from copy import deepcopy
    from functools import cmp_to_key, lru_cache, reduce
    from heapq import heapify, heappop, heappush, heappushpop, nlargest, nsmallest
    from itertools import accumulate, combinations, permutations, count
    from operator import add, iand, ior, itemgetter, mul, xor
    from string import ascii_lowercase, ascii_uppercase, ascii_letters
    from typing import *
    BUFSIZE = 4096

    class FastIO(IOBase):
        newlines = 0

        def __init__(self, file):
            self._fd = file.fileno()
            self.buffer = BytesIO()
            self.writable = 'x' in file.mode or 'r' not in file.mode
            self.write = self.buffer.write if self.writable else None

        def read(self):
            while True:
                b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                if not b:
                    break
                ptr = self.buffer.tell()
                (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
            self.newlines = 0
            return self.buffer.read()

        def readline(self):
            while self.newlines == 0:
                b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                self.newlines = b.count(b'\n') + (not b)
                ptr = self.buffer.tell()
                (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
            self.newlines -= 1
            return self.buffer.readline()

        def flush(self):
            if self.writable:
                os.write(self._fd, self.buffer.getvalue())
                (self.buffer.truncate(0), self.buffer.seek(0))

    class IOWrapper(IOBase):

        def __init__(self, file):
            self.buffer = FastIO(file)
            self.flush = self.buffer.flush
            self.writable = self.buffer.writable
            self.write = lambda s: self.buffer.write(s.encode('ascii'))
            self.read = lambda : self.buffer.read().decode('ascii')
            self.readline = lambda : self.buffer.readline().decode('ascii')
    sys.stdin = IOWrapper(sys.stdin)
    sys.stdout = IOWrapper(sys.stdout)
    input = lambda : sys.stdin.readline().rstrip('\r\n')

    def I():
        return input()

    def II():
        return int(input())

    def MII():
        return map(int, input().split())

    def LI():
        return list(input().split())

    def LII():
        return list(map(int, input().split()))

    def LFI():
        return list(map(float, input().split()))

    def GMI():
        return map(lambda x: int(x) - 1, input().split())

    def LGMI():
        return list(map(lambda x: int(x) - 1, input().split()))
    inf = float('inf')
(dfs, hashing) = (False, False)
if dfs:
    from types import GeneratorType

    def bootstrap(f, stack=[]):

        def wrappedfunc(*args, **kwargs):
            if stack:
                return f(*args, **kwargs)
            else:
                to = f(*args, **kwargs)
                while True:
                    if type(to) is GeneratorType:
                        stack.append(to)
                        to = next(to)
                    else:
                        stack.pop()
                        if not stack:
                            break
                        to = stack[-1].send(to)
                return to
        return wrappedfunc
if hashing:
    RANDOM = random.getrandbits(20)

    class Wrapper(int):

        def __init__(self, x):
            int.__init__(x)

        def __hash__(self):
            return super(Wrapper, self).__hash__() ^ RANDOM

class PrimeTable:

    def __init__(self, n: int) -> None:
        self.n = n
        self.primes = []
        self.max_div = list(range(n + 1))
        self.max_div[1] = 1
        self.phi = list(range(n + 1))
        for i in range(2, n + 1):
            if self.max_div[i] == i:
                self.primes.append(i)
                for j in range(i, n + 1, i):
                    self.max_div[j] = i
                    self.phi[j] = self.phi[j] // i * (i - 1)

    def is_prime(self, x: int):
        if x < 2:
            return False
        if x <= self.n:
            return self.max_div[x] == x
        for p in self.primes:
            if p * p > x:
                break
            if x % p == 0:
                return False
        return True

    def prime_factorization(self, x: int):
        if x > self.n:
            for p in self.primes:
                if p * p > x:
                    break
                if x <= self.n:
                    break
                if x % p == 0:
                    cnt = 0
                    while x % p == 0:
                        cnt += 1
                        x //= p
                    yield (p, cnt)
        while 1 < x and x <= self.n:
            (p, cnt) = (self.max_div[x], 0)
            while x % p == 0:
                cnt += 1
                x //= p
            yield (p, cnt)
        if x >= self.n and x > 1:
            yield (x, 1)

    def get_factors(self, x: int):
        factors = [1]
        for (p, b) in self.prime_factorization(x):
            n = len(factors)
            for j in range(1, b + 1):
                for d in factors[:n]:
                    factors.append(d * p ** j)
        return factors
pt = PrimeTable(10 ** 6)
n = II()
nums = LII()
ans = 1
vis = set()
for _ in range(10):
    v = random.choice(nums)
    if v < ans or v in vis:
        continue
    vis.add(v)
    vals = Counter((math.gcd(v, x) for x in nums))
    for x in pt.get_factors(v):
        if x > ans:
            cnt = 0
            for val in vals:
                if val % x == 0:
                    cnt += vals[val]
            if cnt * 2 >= n:
                ans = max(ans, x)
print(ans)

Solution (Python):
import sys
import heapq
from heapq import *
from math import log2, ceil, floor, gcd, sqrt, log, perm, comb, factorial
from random import randrange
from bisect import bisect_left
from collections import defaultdict, Counter, deque, OrderedDict
from functools import lru_cache, reduce
from bisect import bisect_left, bisect_right
from types import GeneratorType
input = lambda : sys.stdin.buffer.readline().decode().rstrip()

class dict_(dict):
    RANDOM = randrange(2 ** 62)

    def __init__(self, dd):
        super().__init__({k ^ self.RANDOM: v for (k, v) in dd.items()})

    def __missing__(self, key):
        return 0

    def __setitem__(self, key, value):
        super().__setitem__(key ^ self.RANDOM, value)

    def __getitem__(self, item):
        return super().__getitem__(item ^ self.RANDOM)

    def __contains__(self, item):
        return super().__contains__(item ^ self.RANDOM)

    def items(self):
        for (k, v) in super().items():
            yield (k ^ self.RANDOM, v)

    def keys(self):
        for k in super().keys():
            yield (k ^ self.RANDOM)

    def __repr__(self):
        return '{0}'.format({k ^ self.RANDOM: v for (k, v) in super().items()})

def add_edge(node1, node2, graph):
    if node1 not in graph:
        graph[node1] = []
    if node2 not in graph:
        graph[node2] = []
    graph[node1].append(node2)
    graph[node2].append(node1)

class disjointset:

    def __init__(self, n):
        (self.rank, self.parent) = (array('i', [0] * (n + 1)), array('i', [i for i in range(n + 1)]))
        (self.n, self.even) = (n, array('b', [0] * (n + 1)))

    def find(self, x):
        xcopy = x
        while x != self.parent[x]:
            x = self.parent[x]
        while xcopy != x:
            (self.parent[xcopy], xcopy) = (x, self.parent[xcopy])
        return x

    def union(self, x, y):
        (xpar, ypar) = (self.find(x), self.find(y))
        if xpar == ypar:
            return 1
        (par, child) = (xpar, ypar)
        if self.rank[xpar] < self.rank[ypar]:
            (par, child) = (ypar, xpar)
        elif self.rank[xpar] == self.rank[ypar]:
            self.rank[xpar] += 1
        self.parent[child] = par
        self.even[par] |= self.even[child]
        self.n -= 1
        return 0

def dijkstra(graph, start1):
    distances = {node: float('inf') for node in graph}
    distances[start1] = 0
    heap = [(0, start1, [start1])]
    paths = [-1 for i in range(n + 1)]
    while heap:
        (current_distance, current_node, path) = heapq.heappop(heap)
        if current_distance > distances[current_node]:
            continue
        for (neighbor, weight) in graph[current_node]:
            distance = current_distance + weight
            if distance < distances[neighbor]:
                lst = path
                lst.append(neighbor)
                paths[neighbor] = current_node
                distances[neighbor] = distance
                heapq.heappush(heap, (distance, neighbor, lst))
    return (distances, paths)

def mergeSort(arr, n):
    temp_arr = [0] * n
    return _mergeSort(arr, temp_arr, 0, n - 1)

def _mergeSort(arr, temp_arr, left, right):
    inv_count = 0
    if left < right:
        mid = (left + right) // 2
        inv_count += _mergeSort(arr, temp_arr, left, mid)
        inv_count += _mergeSort(arr, temp_arr, mid + 1, right)
        inv_count += merge(arr, temp_arr, left, mid, right)
    return inv_count

def merge(arr, temp_arr, left, mid, right):
    i = left
    j = mid + 1
    k = left
    inv_count = 0
    while i <= mid and j <= right:
        if arr[i] <= arr[j]:
            temp_arr[k] = arr[i]
            k += 1
            i += 1
        else:
            temp_arr[k] = arr[j]
            inv_count += mid - i + 1
            k += 1
            j += 1
    while i <= mid:
        temp_arr[k] = arr[i]
        k += 1
        i += 1
    while j <= right:
        temp_arr[k] = arr[j]
        k += 1
        j += 1
    for loop_var in range(left, right + 1):
        arr[loop_var] = temp_arr[loop_var]
    return inv_count

def Divisors(n):
    divisors = {}
    for num in [n]:
        lst = set()
        i = 1
        while i <= sqrt(num):
            if num % i == 0:
                if num / i == i:
                    lst.add(i)
                else:
                    lst.update([i, num // i])
            i = i + 1
        divisors[num] = list(lst)
    return divisors[num]

def binpow(a, b):
    if b == 0:
        return 1
    res = binpow(a, b // 2)
    res = pow(res, 2, MOD)
    if b % 2:
        return res * a % MOD
    return res

def mod_inverse(a):
    return binpow(a, MOD - 2)

def factors(n):
    if n == 0:
        return set()
    return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def inverse_mod(num):
    a = mod - 2
    result = 1
    result = pow(num, a, mod)
    return result

def mex(arr, N):
    arr1 = arr.copy()
    arr1.sort()
    mex = 0
    for idx in range(N):
        if arr1[idx] == mex:
            mex += 1
    return mex

def mergeDictionary(dict_1, dict_2):
    dict_3 = {**dict_1, **dict_2}
    for (key, value) in dict_3.items():
        if key in dict_1 and key in dict_2:
            dict_3[key] = value + dict_1[key]
    return dict_3

def rindex(lst, value):
    lst.reverse()
    i = lst.index(value)
    lst.reverse()
    return len(lst) - i - 1

def prefix_sum(arr, length_arr, prefix_sum):
    prefix_sum[0] = arr[0]
    for i in range(1, length_arr):
        prefix_sum[i] = prefix_sum[i - 1] + arr[i]

def suffix_sum(arr, length_arr, suffix_sum):
    suffix_sum[length_arr - 1] = arr[length_arr - 1]
    for i in reversed(range(length_arr - 1)):
        suffix_sum[i] = suffix_sum[i + 1] + arr[i]
letters = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']

def bootstrap(f):
    stack = []

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc
mod = 10 ** 9 + 7
import random

def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    random.seed(12312 ^ 42)
    random.shuffle(arr)
    c = Counter(arr)
    half = (n + 1) // 2
    ans = 1
    used = set()
    for x in range(min(n, 7)):
        ar = arr[x]
        if ar in used:
            continue
        used.add(ar)
        g = {}
        for ai in c.keys():
            try:
                g[gcd(ai, ar)] += c[ai]
            except:
                g[gcd(ai, ar)] = c[ai]
        for d in Divisors(ar):
            if d > ans:
                cur = 0
                for (k, v) in g.items():
                    if k % d == 0:
                        cur += v
                        if cur >= half:
                            ans = max(ans, d)
    print(ans)
solve()