Kuroni and the Punishment (Codeforces 1305F)
Tags: Math, probabilities

Kuroni is very angry at the other setters for using him as a theme! As a punishment, he forced them to solve the following problem:You have an array $$$a$$$ consisting of $$$n$$$ positive integers. An operation consists of choosing an element and either adding $$$1$$$ to it or subtracting $$$1$$$ from it, such that the element remains positive. We say the array is good if the greatest common divisor of all its elements is not $$$1$$$. Find the minimum number of operations needed to make the array good.Unable to match Kuroni's intellect, the setters failed to solve the problem. Help them escape from Kuroni's punishment!

Input: The first line contains an integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$)  — the number of elements in the array.The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$. ($$$1 \le a_i \le 10^{12}$$$)  — the elements of the array.

Output: Print a single integer  — the minimum number of operations required to make the array good.

Note: In the first example, the first array is already good, since the greatest common divisor of all the elements is $$$2$$$.In the second example, we may apply the following operations:  Add $$$1$$$ to the second element, making it equal to $$$9$$$.  Subtract $$$1$$$ from the third element, making it equal to $$$6$$$.  Add $$$1$$$ to the fifth element, making it equal to $$$2$$$.  Add $$$1$$$ to the fifth element again, making it equal to $$$3$$$. The greatest common divisor of all elements will then be equal to $$$3$$$, so the array will be good. It can be shown that no sequence of three or less operations can make the array good.

Sample Inputs:
3
6 2 4

5
9 8 7 3 1

Sample Outputs:
0

4

Solution (Python):
from functools import lru_cache
from random import randint
from collections import Counter
from math import gcd

def primeFactors(n):
    assert n >= 1
    factors = Counter()
    while n % 2 == 0:
        factors[2] += 1
        n //= 2
    x = 3
    while x * x <= n:
        while n % x == 0:
            factors[x] += 1
            n //= x
        x += 2
    if n != 1:
        factors[n] += 1
    return factors

def solve(N, A):

    @lru_cache(maxsize=None)
    def getCost(p):
        cost = 0
        for x in A:
            if x < p:
                cost += p - x
            else:
                cost += min(x % p, -x % p)
        return cost
    best = float('inf')
    for i in range(20):
        r1 = randint(0, N - 1)
        r2 = randint(0, N - 1)
        a = A[r1]
        b = A[r2]
        for x in [a - 1, a, a + 1]:
            for y in [b - 1, b, b + 1]:
                if x > 0 and y > 0:
                    for p in primeFactors(gcd(x, y)):
                        best = min(best, getCost(p))
    return best
if __name__ == '__main__':
    (N,) = list(map(int, input().split()))
    A = list(map(int, input().split()))
    ans = solve(N, A)
    print(ans)

Solution (Python):
import random
sieve_primes = []
PRIME_LIMIT = int(1000000.0)
sieve = [False for i in range(0, PRIME_LIMIT)]
for i in range(2, PRIME_LIMIT):
    if not sieve[i]:
        sieve_primes.append(i)
        for j in range(i * i, PRIME_LIMIT, i):
            sieve[j] = True
n = int(input())
arr = list(map(int, input().split()))
primes = set()

def addPrime(num):
    for sieve_prime in sieve_primes:
        if num % sieve_prime == 0:
            primes.add(sieve_prime)
            while num % sieve_prime == 0:
                num //= sieve_prime
    if num > 1:
        primes.add(num)
arr_set = random.sample(arr, len(arr))
arr_set = list(set(arr_set))
for num in arr_set[:8]:
    if num > 1:
        addPrime(num)
    addPrime(num + 1)
    if num > 2:
        addPrime(num - 1)
ans = n

def findAns(prime):
    global ans
    curr_ans = 0
    for num in arr:
        if num < prime:
            curr_ans += prime - num
        else:
            curr_ans += min(num % prime, prime - num % prime)
        if curr_ans >= ans:
            return
    ans = min(curr_ans, ans)
for prime in primes:
    findAns(prime)
    if ans == 0:
        break
print(ans)

Solution (Python):
import random
n = int(input())
best = n
l = list(map(int, input().split()))
candidates = set()
candidates.add(2)

def gcd(x, y):
    while y:
        (x, y) = (y, x % y)
    return x

def factAdd(n):
    for c in candidates:
        while n % c == 0:
            n //= c
    test = 3
    while test * test <= n:
        while n % test == 0:
            candidates.add(test)
            n //= test
        test += 2
    if n > 1:
        candidates.add(n)
for i in range(100):
    a = random.randint(0, n - 1)
    b = random.randint(0, n - 1)
    diff = [-1, 0, 1]
    for d1 in diff:
        a1 = l[a] + d1
        if a1:
            for d2 in diff:
                a2 = l[b] + d2
                if a2:
                    factAdd(gcd(a1, a2))
for cand in candidates:
    count = 0
    for v in l:
        if v <= cand:
            count += cand - v
        else:
            v2 = v % cand
            count += min(v2, cand - v2)
    if count < best:
        best = count
print(best)