Nhận xét 1: Ta chỉ cần thay đổi mỗi phần tử duy nhất ~1~ lần.

Subtask 1:

• Với ~a_i \le 10~, ~LCM(a_i, a_{i+1})~ sẽ chỉ bao gồm nhiều nhất 3 ước nguyên tố thuộc tập ~S = {2, 3, 5}~ sau khi dãy được thay đổi. Từ đó mỗi số ~a_i~ sau khi thay đổi có dạng ~2^x \times 3^y \times 5^z~ với ~0 \le x, y, z \le 2~ ~(1)~.

• Gọi ~dp[i][j]~ là số lần thay đổi các phần tử ít nhất của dãy ~a[1...i]~, với phần tử thứ ~i~ sau khi thay đổi có giá trị là ~j~ ~j~ là các số có dạng ~(1)~.

• Nếu ~j = a_i~, ~dp[i][j]~ = ~min(dp[i - 1][k])~ với ~k~ là số có dạng ~(1)~, ~LCM(j, k)~ là ~SCP~

• Nếu ~j \neq a_i~ và ~a_i~ ~\vert~ ~j~, ~dp[i][j]~ = ~min(dp[i - 1][k])~ ~+~ ~1~ với ~k~ là số có dạng ~(1)~, ~LCM(j, k)~ là ~SCP~.

• Kết quả là ~min(dp[n][j])~.

Độ phức tạp: ~O(N \times 27 \times 27)~.

Subtask 2:

Nhận xét 2: Với mọi phần tử của dãy, ta luôn có thể thay đổi phần tử sao cho LCM của phần tử đó và phần tử liền kề nó là số chính phương.

Chứng minh: Xét phần tử ~a_i~.

• Xét các ước nguyên tố của ~a_{i-1}~ hoặc ~a_i~ gồm ~p_1, p_2, ..., p_k~. Phân tích ~a_{i-1}=~ ~p_1^{x_1} \times p_2^{x_2} \times ... \times p_k^{x_k}~, ~a_i=~ ~p_1^{y_1} \times p_2^{y_2} \times ... \times p_k^{y_k}~. Với ~p_i~, nếu ~max(x_i, y_i)~ lẻ thì ta sẽ nhân ~a_i~ với một lượng ~p_i^{max(x_i, y_i)+1}~. Gọi số ~a_i~ sau thay đổi là ~a_i'~.

• Tiếp tục xét các ước nguyên tố của ~a_i'~ hoặc ~a_{i+1}~ rồi làm như trường hợp trên.

Từ đó ta có cách giải như sau:

• ~dp[i][0/1]~ là số lần thay đổi các phần tử ít nhất của dãy ~a[1...i]~, ~0/1~ là không thay đổi hoặc thay đổi phần tử thứ ~i~.

• Xét ~dp[i][0]~:

  • Nếu ~LCM(a_i, a_{i-1})~ là số chính phương: ~dp[i][0]~ = ~min(dp[i-1][0], dp[i-1][1])~.

  • Nếu không, ~dp[i][0]=~ ~dp[i-1][1]~.

• Xét ~dp[i][1]~: ~dp[i][1]=~ ~min(dp[i - 1][0], dp[i - 1][1])+1~.

Độ phức tạp: ~N \times log(max(a_i))~.

Code mẫu

#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define st first
#define nd second
#define endl "\n"
#define all(v) v.begin(), v.end()
#define Unique(v) v.erase(unique(all(v)), v.end())

using namespace std;

const int MAXN = 1e6 + 5;

int dp[MAXN][2];
int n, a[MAXN];


void PROGRAM(int _){

    cin >> n;

    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }

    auto check = [&] (int i, int j){
        int val = a[i] * a[j] / __gcd(a[i], a[j]);
        return (int)sqrtl(val) * (int)sqrtl(val) == val;
    };


    for (int i = 1; i <= n; i++){
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + 1;
        dp[i][0] = dp[i - 1][1];

        if (check(i - 1, i)){
            dp[i][0] = min(dp[i][0], dp[i - 1][0]);
        }
    }

    cout << min(dp[n][0], dp[n][1]);
}   

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int test = 1;

    for (int _ = 1; _ <= test; _++){
        PROGRAM(_);
    }

    return 0;
}