Function main

CodeChef_problems/Minimum Insertions/solution.cpp:12–69

int ans[200010];

int32_t main() {
	int t;
	cin >> t;

	while (t--) {
		int n;
		cin >> n;

		int prev = 1;
		vector <int> v;
		vector <int> v1;

		for (int i = 0; i < n; i++) {
			int x;
			cin >> x;

			v1.push_back(x);

			if (__gcd(prev, x) > 1) {
				int top = v.back();
				v.pop_back();
				v.push_back(top + 1);
			} else {
				v.push_back(1);
			}

			prev = x;
		}

		if (__gcd(v1[0], v1.back()) > 1 && v.size() == 1) {
			for (int i = 2; i <= n; i++) {
				cout << n / (i - 1) + (n % (i - 1) != 0) << " ";
			}
			cout << endl;
			continue;
		}

		if (__gcd(v1[0], v1.back()) > 1) {
			v[0] += v.back();
			v.pop_back();
		}

		for (int i = 2; i <= n; i++) {
			ans[i] = 0;
		}

		for (int i : v) {
			for (int j = 2; j <= i; j++) {
				ans[j] += (i - 1) / (j - 1);
			}
		}

		for (int i = 2; i <= n; i++) {
			cout << ans[i] << " ";
		}
		cout << endl;
	}
}