AtCoder GCD on blackboard

Problems and Contests
#1

problem link GCD on black board

Can anyone help me to understand this solution.

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n; cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	prefixes[0] = a[0];
	suffixes[n-1] = a[n-1];

	for (int i = 1; i < n; i++) {
		prefixes[i] = gcd(prefixes[i-1], a[i]);
	}
	for (int i = n-2; i >= 0; i--) {
		suffixes[i] = gcd(suffixes[i+1], a[i]);
	}

	ll ret = max(prefixes[n-2], suffixes[1]);
	for (int i = 0; i < n-2; i++) {
		ret = max(ret, gcd(prefixes[i], suffixes[i+2]));
	}
	cout << ret << '\n';
	return 0;
}
#2

I’m assuming the code you’ve posted is the solution you’re referring to? The solution essentially uses the concept of prefix sums to find the greatest common divisor of every possible prefix and suffix of the given array, and then uses that information to find the answer to what the problem is asking for. If you’re not familiar with prefix sums, I’d suggest you check out the USACO Guide section on them.

1 Like