https://beta.atcoder.jp/contests/abc103/tasks/abc103_c
解法
https://beta.atcoder.jp/contests/abc103/submissions/2887427
最適解を考えてみると、(m mod a1)はa1-1となるのが最適。
各項について最適になるようなmを考えてみると、これはlca(a1, a2, ..., aN)-1となる。
これはm = lca(a1, a2, ..., aN)だと、全て0になるが、これから1を引くと、全てai-1になるためである。
a1~aNのlcaを取ると莫大な数になってしまうので、mは求めずに答えだけを求める。
つまり、(a1-1)+(a2-1)+...+(aN-1)が答えになる。
int N, A[3010]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(i, 0, N) cin >> A[i]; int ans = 0; rep(i, 0, N) ans += A[i] - 1; cout << ans << endl; }