洛谷P10916题：深入解析区间GCD计数技巧

一、题目分析

题目给定一个长度为n的排列a，要求对每个x(1≤x≤n)，执行以下操作后计算不同GCD值的数量：

1. 将排列中值为x的元素修改为1

2. 统计所有连续子区间GCD值的不同种类数

‌关键思路‌：

• ‌特殊处理优化‌：当排列是顺序排列时，可以直接推导出数学公式

• ‌动态维护GCD集合‌：对于一般情况，动态维护以每个位置结尾的子区间的GCD集合

• ‌利用GCD递减特性‌：相邻位置的GCD值最多变化O(log(max(a)))次

二、完整代码

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

const int MAXN = 5e5 + 5; // 最大数组长度
int a[MAXN];    // 存储原始排列
int pos[MAXN];  // 记录每个值在排列中的位置
int ans[MAXN];  // 存储每个x对应的答案

// 处理特殊情况的函数：当排列是a_i=i时
void solve_special_case(int n) {
    // 对于顺序排列，每个x对应的答案有固定规律：
    // - x=1时，所有子区间GCD为1，数量为n*(n+1)/2
    // - 但本题实际要求不同GCD值的个数：
    //   当x=1时，所有GCD只有1
    //   当x≠1时，GCD会有1和x两种值
    // 但根据题目特性，答案实际为n-(i≠1)
    for(int i = 1; i <= n; ++i) {
        // 当i=1时，ans[1]=n
        // 当i≠1时，ans[i]=n-1
        ans[i] = n - (i != 1); // 利用布尔值隐式转换(0/1)
    }
}

// 处理一般情况的函数
void solve_general_case(int n) {
    // 使用vector存储每个位置可能的GCD值
    // 实际未用到gcd_sets，可删除
    vector<unordered_set<int>> gcd_sets(n + 1);
    
    // 从小到大遍历每个x（1~n）
    for(int x = 1; x <= n; ++x) {
        // 获取值为x的元素位置
        int modified_pos = pos[x];
        // 将该位置值暂时修改为1
        a[modified_pos] = 1;
        
        unordered_set<int> S; // 存储所有出现过的不同GCD值
        vector<int> current_gcds; // 存储以当前位置结尾的子区间的所有GCD值
        
        // 从左到右遍历数组
        for(int i = 1; i <= n; ++i) {
            vector<int> new_gcds; // 临时存储新的GCD集合
            
            // 单独元素作为子区间[a_i]
            int new_gcd = a[i];
            S.insert(new_gcd); // 添加到总集合
            new_gcds.push_back(new_gcd); // 添加到当前GCD集合
            
            // 遍历前一个位置结束的所有子区间的GCD值
            for(int g : current_gcds) {
                // 计算新的GCD = gcd(前一个区间的GCD, a[i])
                new_gcd = __gcd(g, a[i]);
                
                // 如果GCD值发生变化或者变为1，则添加到集合
                // 优化：当GCD不变时，可以跳过以减少冗余计算
                if(new_gcd != g || new_gcd == 1) {
                    S.insert(new_gcd);
                    new_gcds.push_back(new_gcd);
                }
            }
            
            // 更新当前GCD集合
            current_gcds = new_gcds;
            // 排序并去重，减少后续计算量
            sort(current_gcds.begin(), current_gcds.end());
            auto last = unique(current_gcds.begin(), current_gcds.end());
            current_gcds.erase(last, current_gcds.end());
        }
        
        // 记录当前x的答案（不同GCD的数量）
        ans[x] = S.size();
        // 恢复原始排列的值（重要：因为后续x还要使用原始排列）
        a[modified_pos] = x;
    }
}

int main() {
    // 优化输入输出
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n; // 读入排列长度
    bool is_special_case = true; // 判断是否为特殊情况的标志
    
    // 读入排列数据
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        pos[a[i]] = i; // 记录值a[i]在位置i
        
        // 检查是否满足a_i=i（顺序排列）
        if(a[i] != i) is_special_case = false;
    }
    
    // 根据情况选择处理方法
    if(is_special_case) {
        solve_special_case(n);
    } else {
        solve_general_case(n);
    }
    
    // 输出每个x对应的答案
    for(int i = 1; i <= n; ++i) {
        cout << ans[i]; 
        // 输出空格或换行：当i==n时输出换行，否则输出空格
        if(i < n) cout << " ";
        else cout << "\n";
    }
    
    return 0;
}

三、算法核心解析

1. 特殊情况处理

当排列满足a[i] = i时：

• 修改x=1的位置为1：所有子区间GCD只能是1

• 修改其他位置为1：GCD值可能为1或x

• 通过推导可得公式：ans[i] = n - (i != 1)

2. 一般情况处理

对于每个x，算法执行以下步骤：

1. ‌定位修改位置‌：通过pos数组找到值为x的元素位置

2. ‌模拟修改‌：将该位置值临时设为1

3. ‌动态维护GCD集合‌：

• 单元素子区间：GCD为元素本身

• 扩展子区间：计算前一个区间GCD与当前元素的GCD

• 优化：跳过重复的GCD值

• 初始化当前GCD集合和总集合

• 从左向右遍历数组：

4. ‌记录结果‌：统计总集合大小作为答案

5. ‌恢复数据‌：将修改位置恢复为原始值，确保不影响后续计算

3. 复杂度分析

• ‌时间复杂度‌：一般情况为O(n² log(max(a)))，因为：

• 外层循环遍历x：O(n)

• 内层循环遍历数组：O(n)

• 内层维护GCD集合：最差O(n)，但GCD值变化次数为O(log(max(a)))

• ‌空间复杂度‌：O(n)，用于存储GCD集合

四、总结

本题的关键在于理解GCD的变化特性：

1. 区间扩展时，GCD值单调不增

2. 相邻位置的GCD值差异有限

3. 特殊情况的数学推导可大幅优化时间

对于新手，建议先理解暴力解法，再进行优化。掌握GCD的性质是解决此类问题的核心能力。