codeforces 1732 a. bestie题解

### Codeforces 1732A Bestie 题目解析 对于给定的整数数组 \(a\) 和查询次数 \(q\)，每次查询给出两个索引 \(l, r\)，需要计算子数组 \([l,r]\) 的最大公约数（GCD）。如果 GCD 结果为 1，则返回 "YES"；否则返回 "NO"[^4]。 #### 解决方案概述 为了高效解决这个问题，可以预先处理数据以便快速响应多个查询。具体方法如下： - **预处理阶段**：构建辅助结构来存储每一对可能区间的 GCD 值。 - **查询阶段**：利用已有的辅助结构，在常量时间内完成每个查询。 然而，考虑到内存限制以及效率问题，直接保存所有区间的结果并不现实。因此采用更优化的方法——稀疏表(Sparse Table)，它允许 O(1) 时间内求任意连续子序列的最大值/最小值/GCD等问题，并且支持静态RMQ(Range Minimum Query)/RANGE_GCD等操作。 #### 实现细节 ##### 构建稀疏表 通过动态规划的方式填充二维表格 `st`，其中 `st[i][j]` 表示从位置 i 开始长度为 \(2^j\) 的子串的最大公约数值。初始化时只需考虑单元素情况即 j=0 的情形，之后逐步扩展至更大的范围直到覆盖整个输入序列。 ```cpp const int MAXN = 2e5 + 5; int st[MAXN][20]; // Sparse table for storing precomputed results. vector<int> nums; void build_sparse_table() { memset(st,-1,sizeof(st)); // Initialize the base case where interval length is one element only. for(int i = 0 ;i < nums.size(); ++i){ st[i][0]=nums[i]; } // Fill up sparse table using previously computed values. for (int j = 1;(1 << j)<=nums.size();++j){ for (int i = 0;i+(1<<j)-1<nums.size();++i){ if(i==0 || st[i][j-1]!=-1 && st[i+(1<<(j-1))][j-1]!=-1) st[i][j]=__gcd(st[i][j-1],st[i+(1<<(j-1))][j-1]); } } } ``` ##### 处理查询请求 当接收到具体的 l 和 r 参数后，可以通过查找对应的 log₂(r-l+1) 来定位合适的跳跃步长 k ，进而组合得到最终答案。 ```cpp string query(int L,int R){ int K=(int)(log2(R-L+1)); return __gcd(st[L][K],st[R-(1<<K)+1][K])==1?"YES":"NO"; } ``` 这种方法能在较短时间内完成大量查询任务的同时保持较低的空间开销，非常适合本题设定下的性能需求。