解题思路

给定长度为 n 的数组 a，定义三元组 (i,j,k)（i<j<k）为“好”的充要条件是 三对数的 gcd 要么全部为 1，要么全部大于 1。

关键观察：Ramsey 定理给出 R(3,3)=6——任意 6 个点的完全图二染色（两种颜色分别代表“gcd=1 的边”和“gcd>1 的边”）中，必然存在一个单色三角形。 对应到本题，当 n ≥ 6 时，不管数组取值如何，前 6 个下标中一定存在一个好三元组（三对 gcd 全为 1 或全大于 1）。

据此可将问题大幅简化为常数规模检查：

1. 维护数组 a。每次把 a[p] 改为 x。

2. 令检查集合 S = {1,2,...,min(n,6)}。

   • 若 n ≥ 6，根据 Ramsey 定理，S 中必有一个好三元组；
   • 若 n ≤ 5，只能在全体下标中暴力枚举所有三元组检查（数量最多 C(5,3)=10，完全可行）。

3. 在集合 S（或全体下标）内枚举三元组，计算三对数的 gcd： 若 (g1==1 && g2==1 && g3==1) 或 (g1>1 && g2>1 && g3>1)，输出该三元组； 否则继续。若最终没找到（只会发生在 n≤5 的小规模情形），输出 NO。

算法只做至多 C(6,3)=20 次三元组检查、每次 3 次 gcd，是常数级；即使 q 达到上限也能轻松通过。

复杂度分析

• 每次更新后的检查时间复杂度：O(C(min(n,6),3))，即最多 20 组三元组、常数级。
• 空间复杂度：O(1)（仅用到若干临时变量）。

代码实现

Python

# -*- coding: utf-8 -*-
# ACM 风格：输入输出在主函数；功能封装在外部函数
import sys
from math import gcd

def find_triplet(a, idxs):
    """在给定下标集合 idxs 中寻找任意一个好三元组，返回 (i,j,k) 或 None"""
    m = len(idxs)
    for ii in range(m):
        for jj in range(ii + 1, m):
            for kk in range(jj + 1, m):
                i, j, k = idxs[ii], idxs[jj], idxs[kk]
                g1 = gcd(a[i], a[j])
                g2 = gcd(a[j], a[k])
                g3 = gcd(a[i], a[k])
                # 三对 gcd 全为 1 或 全部 > 1
                if (g1 == 1 and g2 == 1 and g3 == 1) or (g1 > 1 and g2 > 1 and g3 > 1):
                    return (i + 1, j + 1, k + 1)  # 转为 1-based
    return None

def main():
    data = list(map(int, sys.stdin.read().strip().split()))
    it = iter(data)
    n = next(it); q = next(it)
    a = [next(it) for _ in range(n)]
    out_lines = []
    for _ in range(q):
        p = next(it); x = next(it)
        a[p - 1] = x  # 更新
        # 构造检查的下标集合
        if n >= 6:
            idxs = list(range(6))  # 只看前 6 个下标
        else:
            idxs = list(range(n))  # n<=5 时看全部
        ans = find_triplet(a, idxs)
        if ans is None:
            out_lines.append("NO")
        else:
            out_lines.append("YES")
            out_lines.append(f"{ans[0]} {ans[1]} {ans[2]}")
    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

Java

// ACM 风格，类名 Main；使用快速输入避免大数据下超时
import java.io.*;
import java.util.*;

public class Main {

    // 计算两个数的最大公约数（欧几里得算法）
    static int gcd(int a, int b) {
        while (b != 0) {
            int t = a % b;
            a = b;
            b = t;
        }
        return a >= 0 ? a : -a;
    }

    // 在前 limit 个位置中寻找任意一个好三元组；返回 1-based 下标，找不到返回 null
    static int[] findTriplet(int[] a, int limit) {
        for (int i = 0; i < limit; i++) {
            for (int j = i + 1; j < limit; j++) {
                for (int k = j + 1; k < limit; k++) {
                    int g1 = gcd(a[i], a[j]);
                    int g2 = gcd(a[j], a[k]);
                    int g3 = gcd(a[i], a[k]);
                    if ((g1 == 1 && g2 == 1 && g3 == 1) || (g1 > 1 && g2 > 1 && g3 > 1)) {
                        return new int[]{i + 1, j + 1, k + 1};
                    }
                }
            }
        }
        return null;
    }

    // 快速输入
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        int nextInt() throws IOException {
            int c, sgn = 1, x = 0;
            do { c = read(); } while (c <= ' ');
            if (c == '-') { sgn = -1; c = read(); }
            while (c > ' ') {
                x = x * 10 + (c - '0');
                c = read();
            }
            return x * sgn;
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        StringBuilder out = new StringBuilder();

        int n = fs.nextInt();
        int q = fs.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = fs.nextInt();

        for (int t = 0; t < q; t++) {
            int p = fs.nextInt();
            int x = fs.nextInt();
            a[p - 1] = x; // 更新

            int limit = (n >= 6) ? 6 : n;
            int[] ans = findTriplet(a, limit);
            if (ans == null) {
                out.append("NO\n");
            } else {
                out.append("YES\n");
                out.append(ans[0]).append(' ').append(ans[1]).append(' ').append(ans[2]).append('\n');
            }
        }
        System.out.print(out.toString());
    }
}

C++

// ACM 风格：主函数读写；功能放在外部函数
#include <bits/stdc++.h>
using namespace std;

// 在前 limit 个位置中寻找好三元组；返回 {i,j,k} (1-based)，找不到返回空向量
static vector<int> find_triplet(const vector<int>& a, int limit) {
    for (int i = 0; i < limit; ++i) {
        for (int j = i + 1; j < limit; ++j) {
            for (int k = j + 1; k < limit; ++k) {
                int g1 = std::gcd(a[i], a[j]);
                int g2 = std::gcd(a[j], a[k]);
                int g3 = std::gcd(a[i], a[k]);
                // 三对 gcd 全为 1 或 全部 > 1
                if ((g1 == 1 && g2 == 1 && g3 == 1) || (g1 > 1 && g2 > 1 && g3 > 1)) {
                    return {i + 1, j + 1, k + 1};
                }
            }
        }
    }
    return {};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    if (!(cin >> n >> q)) return 0;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    for (int t = 0; t < q; ++t) {
        int p, x;
        cin >> p >> x;
        a[p - 1] = x; // 更新

        int limit = (n >= 6) ? 6 : n;
        auto ans = find_triplet(a, limit);
        if (ans.empty()) {
            cout << "NO\n";
        } else {
            cout << "YES\n";
            cout << ans[0] << ' ' << ans[1] << ' ' << ans[2] << "\n";
        }
    }
    return 0;
}

题目内容

给定一个长度为 $n$ 的数组 $a$ 。一个整数三元组 $(i,j,k)$ 被称为好的当且仅当：

$1≤i<j<k≤n$ ；

其三个元素对应的 $gcd$ 值要么全部为 $1$ ，要么全部大于 $1$ ，使用数学语言表达，即 $max${$gcd(a_i,a_j),gcd(a_j,a_k),gcd(a_i,a_k)$}$=1$ 或 $min$ {$gcd(a_i,a_j),gcd(a_j,a_k),gcd(a_i,a_k)>1$ 。

小美有 $q$ 次对数组 $a$ 的更新。每次更新会给你两个整数 $p$ 和 $x$，代表将 $a_p$ 赋值为 $x$ 。在每一次更新之后，你需要告诉小美是否存在好三元组。如果存在请输出任意一个。

输入描述

第一行输入两个整数 $n,q(3≦n≦2·10^5,1≦q≦2·10^5)$ ，分别表示数组 $a$ 的长度和更新的次数。

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1 ≦ a_i≦ 10^6)$ ，表示初始数组 $a$ 中的元素。

接下来 $q$ 行，第 $i$ 行输入两个整数 $p_i,x_i(1≦p_i≦n,1≦x_i≦10^6)$ ，表示将 $a_{p_i}$ 赋值为 $x_i$ 。

输出描述

对于每次更新，如果在更新后不存在好三元组，则输出一行 $NO$ 。

否则，在第一行输出 $YES$ 。第二行输出三个整数 $(i,j,k)$ ，代表你找到的好三元组。

您可以以任何大小写形式输出答案。例如，字符串 $yEs、yes$ 和 $Yes$ 都将被视为肯定的回答。

样例1

输入

4 3
2 2 3 10
4 3
1 1
1 6

输出

NO
YES
1 2 3
YES
1 3 4

说明

初始数组 $a =${$2,2,3,10$} 。

第一次更新后，$a$ 变为 {$2,2,3,3$}，可以证明不存在好三元组。

第二次更新后，$a$ 变为 {$1,2,3,3$}。$(1,2,3)$ 为一个好三元组，因为 $max(gcd(a_1,a_2),gcd(a_2,a_3),gcd(a_1,a_3))=max(1,1,1)=1$ 。

第三次更新后，$a$ 变为 {$6,2,3,3$}。$(1,3,4)$ 为一个好三元组，因为 $min(gcd(a_1,a_3),gcd(a_3,a_4),gcd(a_1,a_4))= min(3, 3, 3)= 3$ 。