Make Array Good (Codeforces 1762B)
Tags: Others, number theory

An array $$$b$$$ of $$$m$$$ positive integers is good if for all pairs $$$i$$$ and $$$j$$$ ($$$1 \leq i,j \leq m$$$), $$$\max(b_i,b_j)$$$ is divisible by $$$\min(b_i,b_j)$$$.You are given an array $$$a$$$ of $$$n$$$ positive integers. You can perform the following operation:  Select an index $$$i$$$ ($$$1 \leq i \leq n$$$) and an integer $$$x$$$ ($$$0 \leq x \leq a_i$$$) and add $$$x$$$ to $$$a_i$$$, in other words, $$$a_i := a_i+x$$$.  After this operation, $$$a_i \leq 10^{18}$$$ should be satisfied. You have to construct a sequence of at most $$$n$$$ operations that will make $$$a$$$ good. It can be proven that under the constraints of the problem, such a sequence of operations always exists.

Input: Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the length of the array $$$a$$$.The second line of each test case contains $$$n$$$ space-separated integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — representing the array $$$a$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test, output a single integer $$$p$$$ ($$$0 \leq p \leq n$$$) — denoting the number of operations in your solution. In each of the following $$$p$$$ lines, output two space-separated integers — $$$i$$$ and $$$x$$$.You do not need to minimize the number of operations. It can be proven that a solution always exists.

Note: In the first test case, array $$$a$$$ becomes $$$[5,5,5,5]$$$ after the operations. It is easy to see that $$$[5,5,5,5]$$$ is good.In the second test case, array $$$a$$$ is already good.In the third test case, after performing the operations, array $$$a$$$ becomes $$$[10,5,350,5,10]$$$, which is good.In the fourth test case, after performing the operations, array $$$a$$$ becomes $$$[60,10,20]$$$, which is good.

Sample Inputs:
4
4
2 3 5 5
2
4 8
5
3 4 343 5 6
3
31 5 17

Sample Outputs:
4
1 2
1 1
2 2
3 0
0
5
1 3
1 4
2 1
5 4
3 7
3
1 29
2 5
3 3

Solution (Python):
import sys
import copy
import heapq
import bisect
import functools
from math import *
from collections import defaultdict
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import groupby
from itertools import accumulate
from decimal import Decimal, ROUND_HALF_UP
readline = lambda : sys.stdin.readline().rstrip()

def get(n: int):
    return 1 << int(log2(n) + 1)

def solve():
    n = int(readline())
    a = list(map(int, readline().split()))
    print(n)
    for (i, x) in enumerate(a, 1):
        print(i, get(x) - x)

def main():
    t = 1
    t = int(readline())
    for i in range(t):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
import math
import sys
from collections import defaultdict, namedtuple, deque
from itertools import *
read_str = lambda : input()
read_strs = lambda sep=' ': input().split(sep)
read_int = lambda : int(read_str())
read_ints = lambda sep=' ': list(map(int, read_strs(sep)))
write_strs = lambda x, sep=' ': sep.join(list(map(str, x)))

def gcd(a, b):
    if a < b:
        (a, b) = (b, a)
    return a if b == 0 else gcd(b, a % b)

def is_prime(n):
    res = [True] * (n + 1)
    (res[0], res[1]) = (False, False)
    for i in range(2, int(math.sqrt(n))):
        if res[i]:
            for j in range(i + i, n + 1, i):
                res[j] = False
    return res
primes = lambda n, ps: list(filter(lambda x: ps[x], list(range(n + 1))))
p_factors = lambda x, ps: list(filter(lambda y: x % y == 0, ps))
set_nbit = lambda x, n: x | 1 << n
unset_nbit = lambda x, n: x & ~(1 << n)
get_nbit = lambda x, n: (x & 1 << n) >> n
count_set_bits = lambda x: sum((get_nbit(x, n) for n in range(int(math.log2(x)) + 1)))

def lower_bound(a, x, comp=lambda x, y: x <= y):
    n = len(a)
    (i, k) = (0, n)
    while k > 0:
        k //= 2
        while k + i < n and comp(a[k + i], x):
            i += k
    return i + k

def prefix_minmax(arr, func=min):
    res = [arr]
    w = 1
    while w < len(res[-1]):
        curr = res[-1]
        res.append([func(curr[i], curr[i + w]) for i in range(0, len(curr) - w)])
        w <<= 1
    return res

class Node:

    def __init__(self, value, parent=None):
        self.parent = parent if parent else self
        self.left = None
        self.right = None
        self.value = value

class BinaryTree:

    def __init__(self):
        self.root = Node(0)

    def add(self, value):
        node = self.root
        while True:
            if value < node.value:
                if node.left:
                    node = node.left
                else:
                    node.left = Node(value, node)
                    break
            elif node.right:
                node = node.right
            else:
                node.right = Node(value, node)
                break

    def pop_max(self):
        curr = self.root
        while curr.right:
            curr = curr.right
        curr.parent.right = curr.left
        return curr.value

def solve(n, a):
    ai = sorted(enumerate(a), key=lambda x: x[1])
    m = ai[0][1]
    print(n)
    for (i, x) in ai:
        r = (x // m + 1) * m
        print(f'{i + 1} {r - x}')
        m = r
T = read_int()
for _ in range(T):
    N = read_int()
    A = read_ints()
    solve(N, A)

Solution (Python):
for yesh in [*open(0)][2::2]:
    print(len((a := yesh.split())))
    i = 0
    for k in map(int, a):
        i += 1
        print(i, 2 ** len(f'{k:b}') - k)