Pride [Codeforces Round #446 Div1 A]

http://codeforces.com/contest/891/problem/A

N個の配列Aがある。
「並んだ2つの要素(x,y)のどちらかをgcd(A[x],A[y])にする」という操作をする。
全ての要素を1にするための操作の最小回数は？

解法

http://codeforces.com/contest/891/submission/32385209

「1である要素を1つ以上作る」という方針で解いていく。
　
1である要素が1つ以上あり、1でない要素がk個あれば、答えはkとなる。
これは順番に1を伝搬していけばいい。
　
もし無ければ、まず、1を最小回数で作る。
その前にコーナーケースを処理しておこう。
それは、全てのgcdを取った時に1より大きい場合であり、その場合は全てを1にできないので-1を答える。
　
A[L..R]を使って1を作るとすると、gcd(A[L] ... A[R])=1となれば作れる。
gcd(A[L] ... A[R])はR-L回の操作で実現できる。
なので、この区間を全て探索してgcdが1となる最小の操作回数を特定する。
これで1が作れるので後は、他の要素を1に変えればいい。
答えはmin + N - 1となる。

int N, A[2010];
//---------------------------------------------------------------------------------------------------
int solve() {
    int g = 0;
    rep(i, 0, N) g = gcd(g, A[i]);
    if (1 < g) return -1;

    int ok = 0;
    rep(i, 0, N) if (A[i] == 1) ok = 1;
    if (ok) {
        int ans = N;
        rep(i, 0, N) if (A[i] == 1) ans--;
        return ans;
    }

    int mi = 2010;
    rep(L, 0, N) {
        int g = 0;
        rep(R, L, N) {
            g = gcd(g, A[R]);
            if (g == 1) {
                mi = min(mi, R - L);
                break;
            }
        }
    }

    return mi + N - 1;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    cout << solve() << endl;
}