You are given a sequence of integers $A_1, A_2, \ldots, A_N$. This sequence is circular ― for each valid $i$, the element $A_{i+1}$ follows after $A_i$, and the element $A_1$ follows after $A_N$.
You may insert any positive integers at any positions you choose in this sequence; let's denote the resulting sequence by $B$. This sequence is also circular. For each pair of its elements $B_s$ and $B_f$, let's denote the (non-circular) sequence created by starting at $B_s$ and moving from each element to the one that follows after it, until we reach $B_f$, by $B(s, f)$. This sequence includes the elements $B_s$ and $B_f$.
For each $K$ from $2$ to $N$ inclusive, find the smallest possible number of elements that need to be inserted into $A$ to form a sequence $B$ for which there is no subsequence $B(p, q)$ such that:
- The size of $B(p, q)$ is at least $K$.
- There is no pair of consecutive elements in $B(p, q)$ such that their GCD is equal to $1$.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

-----Output-----
For each test case, print a single line containing $N-1$ space-separated integers. For each $i$ ($1 \le i \le N-1$), the $i$-th of these integers should be the smallest number of inserted elements in a valid sequence $B$ for $K = i+1$.

-----Constraints-----
- $1 \le T \le 2,000$
- $2 \le N \le 10^5$
- $1 \le A_i \le 10^9$ for each valid $i$
- the sum of $N$ over all test cases does not exceed $2 \cdot 10^6$

-----Example Input-----
1
5
3 6 4 5 9

-----Example Output-----
3 1 1 0

Source: codechef | Difficulty: VERY_HARD
Tags: Number theory

Mathematics

Constructive algorithms


Solutions:
import math
from collections import defaultdict
t = int(input())
for i in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	j = 0
	res = []
	while j < n:
		if math.gcd(b[j], b[(j + 1) % n]) > 1:
			res.append(1)
		else:
			res.append(0)
		j += 1
	j = 0
	f = 0
	ans = []
	while j < n:
		if res[j] == 0:
			f = 1
			req = j
			break
		j += 1
	if f == 0:
		j = 1
		while j < n:
			ans.append(math.ceil(n / j))
			j += 1
		print(*ans)
	else:
		j = req + 1
		s = 0
		while j % n != req:
			if res[j % n] == 1:
				s += 1
			else:
				if s != 0:
					ans.append(s)
				s = 0
			j += 1
		ans.append(s)
		d = defaultdict(lambda : 0)
		j = 0
		l = len(ans)
		while j < l:
			p = ans[j]
			r = p
			while r >= 1:
				d[r] += p // r
				r += -1
			j += 1
		ans = []
		r = 1
		while r < n:
			ans.append(d[r])
			r += 1
		print(*ans)


from math import gcd
from itertools import groupby

def gcd_split(seq):
	gcds = [int(gcd(a, b) == 1) for (a, b) in zip(seq[1:], seq[:-1])]
	gcds.append(int(gcd(seq[0], seq[-1]) == 1))
	if max(gcds) == 0:
		return -1
	else:
		splits = [len(list(x)) + 1 for (num, x) in groupby(gcds) if num == 0]
		if gcds[0] == gcds[-1] == 0:
			splits[0] += splits[-1] - 1
			splits = splits[:-1]
		return splits
for _ in range(int(input())):
	N = int(input())
	A = [int(x) for x in input().split()]
	split = gcd_split(A)
	res = []
	if split != -1:
		for K in range(2, N + 1):
			temp = (x for x in split if x >= K)
			ins = sum([x // (K - 1) - 1 if x % (K - 1) == 0 else x // (K - 1) for x in temp])
			if ins == 0:
				break
			else:
				res.append(ins)
	else:
		for K in range(2, N + 1):
			ins = N // (K - 1) + (N % (K - 1) > 0)
			if ins == 0:
				break
			else:
				res.append(ins)
	res = res + [0] * (N - 1 - len(res))
	print(*res)


import math
for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	N = n
	G = []
	for i in range(n):
		v = math.gcd(A[i], A[(i + 1) % N])
		if v == 1:
			G.append(1)
		else:
			G.append(0)
	pos = -1
	for i in range(n):
		if G[i] == 1:
			pos = i
			break
	V = []
	ans = [0 for i in range(N - 1)]
	if pos == -1:
		for i in range(N - 1):
			ans[i] = math.ceil(N / (i + 1))
	else:
		c = 0
		for i in range(1, N + 1):
			if G[(pos + i) % N] == 0:
				c = c + 1
			else:
				if c != 0:
					V.append(c)
				c = 0
		for val in V:
			for i in range(min(val, N - 1)):
				ans[i] = ans[i] + val // (i + 1)
	print(*ans)


def gcd(m, n):
	if m > n:
		(a, b) = (n, m)
	else:
		(a, b) = (m, n)
	r = b
	while r > 1:
		r = b % a
		(a, b) = (r, a)
	if r == 0:
		return b
	else:
		return 1

def rlmaker(rl, pc, n):
	d = 1
	for i in range(0, pc + 1):
		if i < n - 1:
			rl[i] += pc // d
			d += 1
	return rl

def rlmakers(rl, pc, n):
	d = 1
	for i in range(0, pc + 1):
		if i < n - 1:
			if pc % d == 0:
				rl[i] += pc // d
			else:
				rl[i] += pc // d + 1
			d += 1
	return rl

def insFinder(n, l):
	lstone = 0
	rl = []
	for i in range(0, n - 1):
		rl.append(0)
	pathli = []
	pc = 0
	start = -1
	end = -1
	c = 0
	for i in range(0, n - 1):
		if gcd(l[i], l[i + 1]) != 1:
			if i == 0:
				start = 0
			if i == n - 2:
				end = n - 1
			if lstone == 1:
				pc += 1
			else:
				lstone = 1
				pc += 1
		elif lstone == 1:
			pathli.append(pc)
			pc = 0
			lstone = 0
	if start == 0:
		if end == n - 1:
			if gcd(l[n - 1], l[0]) != 1:
				pathli.append(pc)
				if len(pathli) > 1:
					pathli[0] += pathli[len(pathli) - 1] + 1
					pathli.remove(pathli[len(pathli) - 1])
				else:
					c = 1
					pathli[0] += 1
			else:
				pathli.append(pc)
		elif gcd(l[n - 1], l[0]) != 1:
			pathli[0] += 1
	elif end == n - 1:
		if gcd(l[n - 1], l[0]) != 1:
			pc += 1
			pathli.append(pc)
		else:
			pathli.append(pc)
	elif gcd(l[n - 1], l[0]) != 1:
		pathli.append(1)
	if c == 1:
		rl = rlmakers(rl, pathli[0], n)
	else:
		for i in range(0, len(pathli)):
			rl = rlmaker(rl, pathli[i], n)
	for i in range(0, n - 1):
		print(rl[i], end=' ')
	print('')
nt = int(input())
for i in range(0, nt):
	n = int(input())
	l = list(map(int, input().strip().split(' ')))
	insFinder(n, l)


import sys, bisect

def gcd(x, y):
	if x % y == 0:
		return y
	return gcd(y, x % y)
input = sys.stdin.readline
t = int(input())
for you in range(t):
	n = int(input())
	l = input().split()
	li = [int(i) for i in l]
	l = []
	for i in range(n):
		l.append(gcd(li[i], li[(i + 1) % n]))
	start = 0
	end = 0
	done = 0
	lo = []
	for i in range(n):
		if l[i] != 1:
			if done:
				end += 1
			else:
				done = 1
				start = i
				end = start
		elif done:
			lo.append((start, end))
			done = 0
	if done:
		lo.append((start, end))
		done = 0
	lfi = []
	if len(lo) == 1 and lo[0][0] == 0 and (lo[-1][1] == n - 1):
		for i in range(2, n + 1):
			z = (n + i - 2) // (i - 1)
			print(z, end=' ')
		continue
	if len(lo) >= 2 and lo[0][0] == 0 and (lo[-1][1] == n - 1):
		size1 = lo[0][1] - lo[0][0] + 1
		size2 = lo[-1][1] - lo[-1][0] + 1
		lfi.append(size1 + size2)
		lo.pop(0)
		lo.pop(-1)
	for i in lo:
		lfi.append(i[1] - i[0] + 1)
	lfi.sort()
	for i in range(2, n + 1):
		k = bisect.bisect_left(lfi, i - 1)
		sum1 = 0
		for j in range(k, len(lfi)):
			sum1 = sum1 + lfi[j] // (i - 1)
		print(sum1, end=' ')
	print()


import math

def gcd(num1, num2):
	if num2 == 0:
		return num1
	else:
		return gcd(num2, num1 % num2)
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	l = []
	sm = []
	p1 = 0
	p2 = 0
	j = 0
	while j < n - 1:
		if gcd(a[j], a[j + 1]) != 1:
			p1 = j + 0
			while j < n - 1 and gcd(a[j], a[j + 1]) != 1:
				j += 1
			p2 = j + 0
			l.append([p1, p2])
			sm.append(p2 - p1 + 1)
		else:
			j += 1
	if len(l) > 0 and l[0][1] - l[0][0] < n - 1:
		if l[-1][1] == n - 1 and l[0][0] == 0:
			if gcd(a[-1], a[0]) != 1:
				sm[0] += sm[-1]
				sm.pop()
		elif gcd(a[-1], a[0]) != 1 and l[0][0] == 0:
			sm[0] += 1
		elif gcd(a[-1], a[0]) != 1 and l[-1][1] == n - 1:
			sm[-1] += 1
		elif gcd(a[-1], a[0]) != 1:
			sm.append(2)
		w = [0] * (n + 1)
		for j in range(len(sm)):
			for k in range(2, sm[j] + 1):
				w[k] += math.ceil((sm[j] - 1) // (k - 1))
		print(*w[2:])
	elif len(l) > 0:
		w = [0] * (n + 1)
		if gcd(a[-1], a[0]) != 1:
			for j in range(len(sm)):
				for k in range(2, sm[j] + 1):
					w[k] += math.ceil((sm[j] - 1) // (k - 1)) + 1
			print(*w[2:])
		else:
			for j in range(len(sm)):
				for k in range(2, sm[j] + 1):
					w[k] += math.ceil((sm[j] - 1) // (k - 1))
			print(*w[2:])
	else:
		w = [0] * (n + 1)
		if gcd(a[-1], a[0]) != 1:
			w[2] = 1
			print(*w[2:])
		else:
			print(*w[2:])