Mike and gcd problem

发表于 分类于 ，

    给出一个长度为n的数组，n>2。

    当一个数组的最大公约数为大于1时则为美丽数组。

    每次操作可以让相邻的两个数$a_i$与$a_{i+1}$分别重新赋值为$a_i-a_{i+1}$和$a_i+a_{i+1}$。

    问最少多少次操作可以使得数组变为美丽数组。

Mike and gcd problem

Created by LXC on Sun Jun 25 23:29:49 2023

https://codeforces.com/problemset/problem/798/C

ranting: 1700

tag: dp, greedy, number theory

problem

给出一个长度为n的数组，n>2。

当一个数组的最大公约数为大于1时则为美丽数组。

每次操作可以让相邻的两个数$a_i$与$a_{i+1}$分别重新赋值为$a_i-a_{i+1}$和$a_i+a_{i+1}$。

问最少多少次操作可以使得数组变为美丽数组。

solution

猜测结论，当数组不为美丽数组可以通过操作变为美丽数组。

因为两个相邻的数都是奇数则一次操作后都变偶数；当为一奇一偶则一次操作变成两个奇数。

所以理论上所有数都可以变成偶数。因此最大公约数可以大于1。

我们统计每个连续奇数的子段长度。不妨设共有k段，第i段的长度为$len_i$。

对于$len_i$为偶数则只需要$\frac{len_i}{2}$次操作；对于$len_i$为奇数数则只需要$\frac{len_i-1}{2}$次操作基础上再加两次；

所以答案为$\sum \limits_{i=1}^{k}( \lfloor \frac{len_i}{2} \rfloor + 2 \times len_i \bmod 2)$

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n;
    cin >> n;
    vector<ll> a(n);
    ll g = 0;
    for (auto& i : a)
        cin >> i, g = __gcd(g, i);
    cout << "YES\n";
    if (g > 1) {
        cout << "0\n";
    } else {
        int ans = 0;
        for (int i = 0, p; i < n; i++) {
            p = i;
            while (i < n && a[i] % 2)
                i++;
            ans += (i - p) / 2 + (i - p) % 2 * 2;
        }
        cout << ans << "\n";
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}