logoChat01.ai

Ошибки в коде

創建於：2025年3月7日

使用 GPT-4o 回答 Chat01

問題

в чем ошибка в коде этой задачи?
G. Взаимно простой отрезок
ограничение по времени на тест1 секунда
ограничение по памяти на тест1024 мегабайта
Дан массив из n
чисел ai
. Скажем, что отрезок этого массива a[l..r]
(1≤l≤r≤n
) хороший, если на этом отрезке НОД всех чисел равен 1
. Ваша задача — найти самый короткий хороший отрезок.

Входные данные
Первая строка содержит целое число n
(1≤n≤105
). Вторая строка содержит числа ai
(1≤ai≤1018
).

Выходные данные
Выведите одно число — минимальную длину хорошего отрезка. Если хорошего отрезка не существует, выведите −1
.
код:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pf push_front

#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

using namespace std;
using namespace __gnu_pbds;

template<class T> using order_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template<class T> using order_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

//--------------------------------------------------------------------------------------------//

const ll INF=1e18;
const ll MOD=1e9+7;

ll sz=1;
vector<ll>t;

void build(ll x=0,ll lx=0,ll rx=sz){
if (rx-lx==1){return ;}
ll mid=(lx+rx)/2;
build(x2+1,lx,mid);
build(x2+2,mid,rx);
t[x]=__gcd(t[x2+1],t[x2+2]);
}

ll get(ll l,ll r,ll x=0,ll lx=0,ll rx=sz){
if (l>=rx||lx>=r){return 0;}
if (lx>=l&&rx<=r){return t[x];}
ll mid=(lx+rx)/2;
return __gcd(get(l,r,x2+1,lx,mid),get(l,r,x2+2,mid,rx));
}

void solve(){
ll n,r=0,ans=INF;
cin>>n;
while (sz<n)sz*=2;
t.resize(sz*4);
vector<ll>a(n);
for (int i=0;i<n;i++){
cin>>a[i];
t[sz+i-1]=a[i];
}
build();
for (int l=0;l<n;l++){
while (r<n&&get(l,r+1)!=1)r++;
if (get(l,r+1)==1){ans=r-l+1;}
}
cout<<(ans==INF?-1:ans);
}

//--------------------------------------------------------------------------------------------//

int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
ll tt=1;
//cin>>tt;
while (tt--){
solve();
}
return 0;
}

回答

В коде есть несколько ошибок и потенциальных проблем, которые могут приводить к некорректной работе:

1. Ошибка при заполнении сегментного дерева

В этом фрагменте:

cpp
for (int i = 0; i < n; i++) {
    cin >> a[i];
    t[sz + i - 1] = a[i];
}
  • Ошибка: t[sz + i - 1] = a[i]; — неправильный индекс. Должно быть t[sz + i] = a[i];, потому что нумерация в массиве t начинается с sz, а не sz - 1.

2. Ошибка в логике обновления ans

Этот фрагмент:

cpp
if (get(l, r+1) == 1) { ans = r - l + 1; }
  • Ошибка: ans обновляется каждый раз, но не сохраняет минимальное значение. Нужно заменить = на min:
cpp
if (get(l, r+1) == 1) { ans = min(ans, r - l + 1); }

3. Ошибка в логике выхода за границы массива

В этом фрагменте:

cpp
while (r < n && get(l, r+1) != 1) r++;
if (get(l, r+1) == 1) { ans = r - l + 1; }
  • Ошибка: Когда r == n - 1 и выполняется r++, то get(l, r+1) обращается к r + 1, что выходит за границы массива. Нужно добавить проверку перед вызовом get:
cpp
while (r < n && get(l, r+1) != 1) r++;
if (r < n && get(l, r+1) == 1) { ans = min(ans, r - l + 1); }

4. Ошибка в построении дерева build

Функция build() не инициализирует листья перед рекурсивным вызовом. Нужно заполнить листья перед построением:

cpp
void build() {
    for (int i = sz - 1; i > 0; i--)
        t[i] = __gcd(t[i * 2], t[i * 2 + 1]);
}

И перед вызовом build() заполнить листья:

cpp
for (int i = 0; i < n; i++)
    t[sz + i] = a[i];

Исправленный код

cpp
#include <bits/stdc++.h>
using namespace std;

#define ll long long
const ll INF = 1e18;

ll sz = 1;
vector<ll> t;

void build() {
    for (int i = sz - 1; i > 0; i--)
        t[i] = __gcd(t[i * 2], t[i * 2 + 1]);
}

ll get(ll l, ll r, ll x = 1, ll lx = 0, ll rx = sz) {
    if (l >= rx || lx >= r) return 0;
    if (lx >= l && rx <= r) return t[x];
    ll mid = (lx + rx) / 2;
    return __gcd(get(l, r, x * 2, lx, mid), get(l, r, x * 2 + 1, mid, rx));
}

void solve() {
    ll n, r = 0, ans = INF;
    cin >> n;
    while (sz < n) sz *= 2;
    t.assign(sz * 2, 0);
    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        t[sz + i] = a[i]; 
    }
    build();

    for (int l = 0; l < n; l++) {
        while (r < n && get(l, r + 1) != 1) r++;
        if (r < n && get(l, r + 1) == 1) {
            ans = min(ans, r - l + 1);
        }
    }

    cout << (ans == INF ? -1 : ans);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

Что исправлено?

  1. Правильное построение сегментного дерева (build).
  2. Правильное заполнение массива t в solve().
  3. Добавлена проверка r < n перед вызовом get(l, r+1).
  4. Используется min(ans, r - l + 1) для корректного обновления минимального отрезка.

Теперь код корректно находит минимальный "хороший" отрезок.

分享這個問答