Submission #69712099

---

Source Code Expand

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); i++)
#define R(i, j, k) for(int i = (j); i >= (k); i--)
#define ll long long
#define sz(a) ((int) a.size())
#define vi vector<int>
#define pb emplace_back
#define me(a, x) memset(a, x, sizeof(a))
using namespace std;
const int N = 1e6 + 7, mod = 998244353, inv2 = (mod + 1) / 2;
int n;
ll a[N];
ll ans;
void solve(vector<ll>a, ll inc) {
	if(inc + a[0] > ans) {
		return;
	}
	


}
void Main() {
	cin >> n;
	L(i, 1, n) {
		cin >> a[i];
	}
	ans = a[1] + a[2];
	sort(a + 1, a + n + 1);
	ll inc = 0;
	while(true) {
		if(a[1] + inc >= ans) break;
		L(i, 2, n) {
			ans = min(ans, a[1] + a[i] - __gcd(a[1], a[i]) + inc);
		}
		if(a[1] == a[2]) break;
		ll dv = (a[2] - 1) / a[1];
		inc += dv * a[1];
		L(i, 2, n) a[i] -= dv * a[1];
		sort(a + 1, a + n + 1);
	}
	cout << ans << '\n';
}
int main() {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t; cin >> t; while(t--) Main();
	return 0;
}

Submission Info

Judge Result