Заметим, что существует два варианта какие числа брать, чтобы их сумма была нечётной: $$$3$$$ нечетных числа; $$$2$$$ четных и $$$1$$$ нечетное. Сохраним все индексы четных и нечетных чисел в два массива, и проверим оба случая.

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    odd, even = [], []
    for i in range(n):
        if a[i] % 2 == 0:
            even.append(i + 1)
        else:
            odd.append(i + 1)
    if len(odd) >= 1 and len(even) >= 2:
        print("YES")
        print(odd[0], even[0], even[1])
    elif len(odd) >= 3:
        print("YES")
        print(odd[0], odd[1], odd[2])
    else:
        print("NO")
        
t = int(input())
for test in range(t):
    solve()

#include <bits/stdc++.h>

using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> odd, even;
        for (int i = 1; i <= n; i++) {
            int x;
            cin >> x;
            if (x % 2 == 0) {
                even.push_back(i);
            } else {
                odd.push_back(i);
            }
        }
        if (odd.size() >= 3) {
            cout << "YES\n";
            cout << odd[0] << " " << odd[1] << " " << odd[2] << '\n';
        } else if (odd.size() >= 1 && even.size() >= 2) {
            cout << "YES\n";
            cout << odd[0] << " " << even[0] << " " << even[1] << '\n';
        } else {
            cout << "NO\n";
        }
    }
}

Давайте заметим, что нам не имеет смысла разбивать больше, чем на $$$k = 2$$$ подотрезков. Докажем это.

Пусть мы как — то разбили массив $$$a$$$ на $$$m \gt 2$$$ подотрезков : $$$b_1, b_2, \ldots, b_m$$$. Заметим, что $$$\gcd(b_1, b_2, \ldots, b_m) \le \gcd(b_1 + b_2, b_3, \ldots, b_m)$$$, так как если $$$b_1$$$ и $$$b_2$$$ были кратны $$$\gcd(b_1, b_2 , \ldots, b_m)$$$, значит и $$$b_1 + b_2$$$ тоже кратно $$$\gcd(b_1, b_2, \ldots, b_m)$$$. А значит, мы можем вместо $$$b_1$$$ и $$$b_2$$$ использовать $$$b_1 + b_2$$$, и ответ не ухудшится, таким образом, всегда выгодно использовать не более $$$k = 2$$$ подотрезков.

Как найти ответ? Пусть $$$s$$$ — сумма массива $$$a$$$. Давайте допустим $$$pref_i = {\sum_{j = 1}^{i} a_j}$$$, тогда ответ это $$$\max\limits_{1 \le i \lt n}(\gcd(pref_i, s - pref_i)$$$.

from math import gcd
t = int(input())
for test in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    s = 0
    for i in range(n):
        s += a[i]
    ans = 0
    pref = 0
    for i in range(n - 1):
        pref += a[i]
        ans = max(ans, gcd(pref, s - pref))
    print(ans)

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        long long s = accumulate(a.begin(), a.end(), 0ll), cur = 0;
        long long ans = 1;
        for (int i = 0; i < n - 1; i++) {
            cur += a[i], s -= a[i];
            ans = max(ans, __gcd(s, cur));
        }
        cout << ans << "\n";
    }
}

У этой задачи есть два похожих решения, мы расскажем оба.

t = int(input())
def ask (x):
	print('-', x)
	return int(input())
for i in range(t):
	cur = int(input())
	add = 0
	ans = 0
	while cur > 0:
		x = ask(add + 1)
		back = x - cur + 1
		add = 2 ** back - 1
		ans += 2 ** back
		cur = x - back
	print('!', ans)

#include <iostream>
 
using namespace std;
 
int ask (int x) {
    cout << "- " << x << endl;
    if (x == -1)
        exit(0);
    cin >> x;
    return x;
}
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int cnt;
        cin >> cnt;
        int n = 0;
        int was = 0;
        while (cnt > 0) {
            n += 1;
            int nw = ask(1 + was);
            int back = nw - cnt + 1;
            n += (1 << back) - 1;
            was = (1 << back) - 1;
            cnt = nw - back;
        }
        cout << "! " << n << endl;
    }
}

Давайте зафиксируем $$$g$$$ и проверим, что ребро веса $$$g$$$ существует в $$$G'$$$. Первое число, которое делится на $$$g$$$, начиная с $$$L$$$ — $$$\lceil \frac{L}{g} \rceil \cdot g$$$, а второе — $$$(\lceil \frac{L}{g} \rceil + 1) \cdot g$$$, заметим что их $$$gcd$$$ равен $$$g$$$, то есть ребро между этими вершинами имеет вес $$$g$$$. Если второе число больше $$$R$$$, то ребра веса $$$g$$$ в графе $$$G'$$$ не существует, потому что на отрезке с $$$L$$$ по $$$R$$$ максимум только одна вершина, которая делится на $$$g$$$. То есть надо посчитать количество таких $$$g$$$, что $$$(\lceil \frac{L}{g} \rceil + 1) \cdot g \leq R$$$.

Рассмотрим $$$g \geq L$$$, тогда $$$(\lceil \frac{L}{g} \rceil + 1) \cdot g = 2 \cdot g$$$. Получаем верхнее ограничение на $$$g \leq \lfloor \frac{R}{2} \rfloor$$$. То есть $$$L \leq g \leq \lfloor \frac{R}{2} \rfloor$$$ — удовлетворяют.

Остались $$$g \lt L$$$.

Заметим, что $$$\lceil \frac{L}{g} \rceil$$$ принимает $$$O(\sqrt{L})$$$ значений. Тогда зафиксируем какое-то $$$f = \lceil \frac{L}{g} \rceil$$$, заметим, что $$$f$$$ соответствует последовательный отрезок значений $$$l \leq g \leq r$$$. Будем перебирать такие отрезки, поскольку их столько же, сколько и различных значений $$$f$$$, то есть $$$O(\sqrt{L})$$$. Тогда, если есть левая граница отрезка $$$l$$$, можно найти $$$r$$$ либо бинарным поиском, либо расписать формулу. Следующая левая граница будет просто $$$r + 1$$$. Тогда заметим, что если зафиксировано $$$f$$$, то $$$(f + 1) \cdot g \leq R$$$ равноценно $$$g \leq \lfloor \frac{R}{f + 1} \rfloor$$$. То есть при фиксированном отрезке с $$$l$$$ по $$$r$$$, $$$g$$$ удовлетворяет ограничению $$$l \leq g \leq min(r, \lfloor \frac{R}{f + 1} \rfloor)$$$. Тогда переберем все такие отрезки и просуммируем по ним хорошие $$$g$$$.

Тогда получается решение за $$$O(\sqrt{L})$$$ или $$$O(\sqrt{L} \cdot log(L))$$$, что, если аккуратно написать, тоже проходит.

def solve():
    L, R = map(int, input().split())
    ans = max(0, R // 2 - L + 1)
    left = 1
    while left < L:
        C = (L + left - 1) // left
        right = (L + C - 2) // (C - 1) - 1
        ans += max(0, min(right, R // (C + 1)) - left + 1)
        left = right + 1
    print(ans)
t = int(input())
for test in range(t):
    solve()

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    for (int test_case = 0; test_case < t; test_case++){
        ll L, R;
        cin >> L >> R;
        ll ans = max(0ll, R / 2 - L + 1);
        for (ll left = 1, right; left < L; left = right + 1){
            ll C = (L + left - 1) / left;
            right = (L + C - 2) / (C - 1) - 1;
            ans += max(0ll, min(right, R / (C + 1)) - left + 1);
        }
        cout << ans << '\n';
    }
}

Отсортируем массив и будем обрабатывать тройки $$$i, j, k$$$, считая что $$$i \lt j \lt k$$$ и $$$a_i \lt a_j \lt a_k$$$. Теперь если $$$gcd(a_i, a_k) = 1$$$, то количество способов взять индекс $$$j$$$ равно $$$k - i - 1$$$.

Будем считать ответ на задачу для каждого $$$k$$$ от $$$1$$$ до $$$n$$$, считая что $$$a_k$$$ — максимальное число в тройке. Теперь пусть $$$c$$$ — количество чисел, взаимно простых с $$$a_k$$$ на префиксе от $$$1$$$ до $$$k - 1$$$, а $$$sum$$$ — сумма их индексов. Тогда к ответу нужно прибавить $$$c \cdot i - sum - c$$$.

Осталось узнавать количество чисел, взаимно простых с $$$a_k$$$ и сумму их индексов. Это можно делать с помощью метода включений и исключений. Пусть $$$cnt_i$$$ — количество чисел $$$a_j$$$, которые делятся на $$$i$$$, $$$s_i$$$ — сумма индексов $$$j$$$ чисел $$$a_j$$$, которые делятся на $$$i$$$. Посмотрим на простые числа $$$p_1, p_2, ..., p_m$$$, входящие в факторизацию числа $$$a_k$$$.

Тогда пусть изначально $$$c$$$ равно количеству чисел на префиксе, а $$$sum$$$ сумме индексов на префиксе. Заметим, что тогда мы учли лишние элементы — числа, которые делятся на $$$p_1, p_2, ..., p_m$$$, так как они будут не взаимно просты с $$$a_k$$$, вычтем их из $$$c$$$ и $$$sum$$$. Но сделав это мы опять же учли лишние элементы, кратные числам вида $$$p_i * p_j$$$, где $$$i \neq j$$$, прибавим их обратно и т.д. Таким образом мы можем перебрать маску $$$mask$$$ простых чисел $$$p_1, p_2, ..., p_m$$$. И в зависимости от четности битов в маске будем вычитать или прибавлять элементы, кратные $$$d$$$, , где $$$d$$$ — произведение простых, входящих в $$$mask$$$. Получив $$$c$$$ и $$$sum$$$ мы можем пересчитать ответ для позиции $$$i$$$.

Чтобы перейти от позиции $$$i$$$ к позиции $$$i+1$$$, обновим значения $$$cnt$$$ и $$$s$$$, добавив элемент $$$a_{i-1}$$$ с помощью перебора маски простых элемента $$$a_{i-1}$$$.

#include "bits/stdc++.h"
 
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
 
#define sz(v) ((int)(v).size())
#define all(a) (a).begin(),  (a).end()
#define rall(a) a.rbegin(), a.rend()
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define time ((double)clock() / (double)CLOCKS_PER_SEC)
 
using pii = pair<int, int>;
using ll = long long;
using int64 = long long;
using ld = double;
 
const ll infll = (ll) 1e18 + 27;
const ll inf = (ll) 1e9;
 
#define dbg(x) cout << #x << " = " << (x) << endl
 
template<class T>
using pq = priority_queue<T, vector<T>, less<T>>;
template<class T>
using pqr = priority_queue<T, vector<T>, greater<T>>;
 
template<typename T, typename T2>
istream &operator>>(istream &in, pair<T, T2> &b) {
    in >> b.first >> b.second;
    return in;
}
 
template<typename T, typename T2>
ostream &operator<<(ostream &out, const pair<T, T2> &b) {
    out << "{" << b.first << ", " << b.second << "}";
    return out;
}
 
template<typename T>
istream &operator>>(istream &in, vector<T> &b) {
    for (auto &v : b) {
        in >> v;
    }
    return in;
}
 
template<typename T>
ostream &operator<<(ostream &out, vector<T> &b) {
    for (auto &v : b) {
        out << v << ' ';
    }
    return out;
}
 
template<typename T>
ostream &operator<<(ostream &out, deque<T> &b) {
    for (auto &v : b) {
        out << v << ' ';
    }
    return out;
}
 
template<typename T>
void print(T x, string end = "\n") {
    cout << x << end;
}
 
 
template<typename T1, typename T2>
bool chkmin(T1 &x, const T2 &y) { return x > y && (x = y, true); }
 
template<typename T1, typename T2>
bool chkmax(T1 &x, const T2 &y) { return x < y && (x = y, true); }
 
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
 
const int N = 3e5 + 10;
 
ll s[N];
ll cnt[N];
 
ll d[N][20];
int ptr[N];
bool u[N];
 
ll Cnt = 0;
ll Sum = 0;
 
ll Ans = 0;
 
void Answer (int x, int pos) {
	ll C = Cnt;
	ll X = Sum;
	int K = (1ll << ptr[x]);
	for (int mask = 1; mask < K; mask++) {
		ll k = 1;
		for (int j = 0; j < ptr[x]; j++) {
			if ((mask >> j) & 1) {
				k *= d[x][j];
			}
		}
		int bits = __builtin_popcount(mask);
		int D = k;
		if (bits % 2 == 1) {
			C -= cnt[D];
			X -= s[D];
		} else {
			C += cnt[D];
			X += s[D];
		}
	}
	Ans += C * pos - X;
}
 
void add (int x, int pos) {
	Cnt += 1;
	Sum += pos + 1;
	auto v = d[x];
	int K = (1ll << ptr[x]);
	for (int mask = 1; mask < K; mask++) {
		ll k = 1;
		for (int j = 0; j < ptr[x]; j++) {
			if ((mask >> j) & 1) {
				k *= d[x][j];
			}
		}
		int D = k;
		s[D] += pos + 1;
		cnt[D] += 1;
	}
}
 
void solve() {
	for (int i = 2; i < N; i++) {
		if (!u[i]) {
			for (int j = i; j < N; j += i) {
				u[j] = true;
				d[j][ptr[j]] = i;
				ptr[j]++;
			}
		}
	}
	int n;
	cin >> n;
	vector<int> a(n);
	cin >> a;
	sort(all(a));
	for (int i = 0; i < n; i++) {
		Answer(a[i], i);
		if (i > 0) {
			add(a[i - 1], i - 1);
		}
	}
	cout << Ans << "\n";
}
 
int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    solve();
    return 0;
}

Эта задача имеет несколько решений, использующих разные суффиксные структуры. Мы расскажем два из них — использующее суффиксный массив, и использующее суффиксный автомат.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<int> suffix_array(string s){
    int n = s.size();
    vector<int> a(n), c(n), h(n);
    vector<pair<char, int>> t;
    for (int i = 0; i < n; i++) t.push_back({s[i], i});
    sort(t.begin(), t.end());
    int cur = -1;
    for (int i = 0; i < n; i++){
        if (i == 0 || t[i].first != t[i - 1].first){
            cur++;
            h[cur] = i;
        }
        a[i] = t[i].second;
        c[a[i]] = cur;
    }
    vector<int> a1(n), c1(n);
    for (int len = 1; len < n; len *= 2){
        for (int i = 0; i < n; i++){
            int j = (n + a[i] - len) % n;
            a1[h[c[j]]++] = j;
        }
        a = a1;
        cur = -1;
        for (int i = 0; i < n; i++){
            if (i == 0 || c[a[i]] != c[a[i - 1]] || c[(a[i] + len) % n] != c[(a[i - 1] + len) % n]){
                cur++;
                h[cur] = i;
            }
            c1[a[i]] = cur;
        }
        c = c1;
    }
    return a;
}
vector<int> build_lcp(string s, vector<int> suf){
    int n = s.size();
    vector<int> rsuf(n), lcp(n);
    for (int i = 0; i < n; i++) rsuf[suf[i]] = i;
    int cur = 0;
    for (int i = 0; i < n; i++){
        int j = rsuf[i];
        if (j != n - 1){
            while (s[suf[j] + cur] == s[suf[j + 1] + cur]) cur++;
            lcp[j] = cur;
        }
        if (cur > 0) cur--;
    }
    return lcp;
}
const int N = 1e6 + 1;
int r[N], l[N], us[N], cnt[N];
vector<int> pos[N];

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n;
    cin >> n;
    string s;
    cin >> s;
    s += '$';
    vector<int> suf = suffix_array(s);
    vector<int> lcp = build_lcp(s, suf);
    for (int i = 0; i < lcp.size(); i++) {
        pos[lcp[i]].push_back(i);
    }
    ll ans = n;
    for (int k = n; k >= 2; k--) {
        for (int i : pos[k]) {
            // add i
            us[i] = true;
            cnt[1]++;
            l[i] = r[i] = i;
            if (i != 0 && us[i - 1]) {
                cnt[i - l[i - 1]]--;
                cnt[1]--;
                cnt[i - l[i - 1] + 1]++;
                l[i] = l[i - 1];
                r[l[i - 1]] = i;
            }
            if (i + 1 < lcp.size() && us[i + 1]) {
                cnt[r[i + 1] - i]--;
                cnt[i - l[i] + 1]--;
                cnt[r[i + 1] - l[i] + 1]++;
                l[r[i + 1]] = l[i];
                r[l[i]] = r[i + 1];
            }
        }
        for (int x = k; x <= n; x += k) {
            ans += 1ll * x * cnt[x - 1];
        }
    }
    cout << ans << "\n";
}

/* Includes */
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>

/* Using libraries */
using namespace std;

/* Defines */
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ld long double
#define pb push_back
#define vc vector
#define sz(a) (int)a.size()
#define forn(i, n) for (int i = 0; i < n; ++i)
#define pii pair <int, int>
#define vec pt
#define all(a) a.begin(), a.end()

const int K = 26;
const int N = 1e6 + 1;

struct node {
    int next[K];
    int suf = -1, pr = -1, dp = 0, len = 0, ch = -1;
    node () {
        forn (i, K) next[i] = -1;
    }
};

int get (char c) {
    if (c >= 'a')
        return c - 'a';
    return c - 'A';
}

int lst = 0, sz = 1;
node t[N * 2];
int used[N * 2];

int add (int a, int x) {
    int b = sz++;
    t[b].pr = a;
    t[b].suf = 0;
    t[b].ch = x;
    for (; a != -1; a = t[a].suf) {
        if (t[a].next[x] == -1) {
            t[a].next[x] = b;
            t[b].len = max(t[b].len, t[a].len + 1);
            continue;
        }
        int c = t[a].next[x];
        if (t[c].pr == a) {
            t[b].suf = c;
            break;
        }
        int d = sz++;
        forn (i, K) t[d].next[i] = t[c].next[i];
        t[d].suf = t[c].suf;
        t[c].suf = t[b].suf = d;
        t[d].pr = a;
        t[d].ch = x;
        for (; a != -1 && t[a].next[x] == c; a = t[a].suf) {
            t[a].next[x] = d;
            t[d].len = max(t[d].len, t[a].len + 1);
        }
        break;
    }
    return b;
}

void add (char c) {
    lst = add(lst, get(c));
}

void dfs (int u) {
    used[u] = 1;
    for (int i = 0; i < K; ++i) {
        if (t[u].next[i] == -1) continue;
        int v = t[u].next[i];
        if (!used[v])
            dfs(v);
        t[u].dp += t[v].dp;
    }
}

vc <int> p[N], pr;
int dr[N];
vc <pii> d;
int l, r, cur = 0;

int cnt_log (int x, int y) {
    int z = 1, res = 0;
    while (y >= z) {
        z *= x;
        ++res;
    }
    return res - 1;
}

void rec (int i, int x) {
    if (i == sz(d)) {
        cur += l <= x;
        return;
    }
    rec(i + 1, x);
    for (int j = 1; j <= d[i].second; ++j) {
        x *= d[i].first;
        if (x > r)
            break;
        rec(i + 1, x);
    }
}

void solve () {
    int n;
    cin >> n;
    string s;
    cin >> s;
    for (char c : s)
        add(c);
    for (int a = lst; a != -1; a = t[a].suf)
        t[a].dp = 1;
    dfs(0);
    for (int i = 2; i <= n; ++i) {
        if (dr[i] == 0) {
            dr[i] = i;
            pr.pb(i);
        }
        for (int j = 0; j < sz(pr) && pr[j] <= dr[i] && i * pr[j] <= n; ++j)
            dr[i * pr[j]] = pr[j];
    }
    long long ans = 0;
    forn (i, sz) {
        if (t[i].len == 0) continue;
        l = t[t[i].suf].len + 1;
        r = t[i].len;
        int x = t[i].dp;
        d.clear();
        while (x > 1) {
            int y = dr[x];
            if (d.empty() || d.back().first != y)
                d.pb({y, 1});
            else
                d.back().second++;
            x /= y;
        }
        rec(0, 1);
        ans += t[i].dp * cur;
        cur = 0;
    }
    cout << ans << '\n';
}

/* Starting and precalcing */
signed main() {
    /* freopen("input.txt","r",stdin);freopen("output.txt","w",stdout); */
    fast;
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}