はまやんはまやんはまやん

hamayanhamayan's blog

解法

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;
}