洛谷P10916题解：动态规划与数学优化的解题思路与代码实现

一、题目解读

洛谷P10916题是一道典型的算法竞赛题目，要求根据给定的数列a，计算每个位置x对应的答案ans[x]。题目核心在于分析数列元素的特性，通过动态规划与数学优化策略，高效求解每个位置对应的答案。该题目考验选手对GCD（最大公约数）计算、集合维护及特殊情况处理的综合能力。

二、解题思路

解题思路分为两部分：特殊情况和一般情况。

1. 特殊处理（当a_i = i时）：

若数列a满足每个元素a[i]等于其下标i（即a_i=i），则答案可直接通过数学规律推导。此时ans[i] = n - (i!= 1)，即除首元素外，其余答案均为n-1。该特殊情况简化了计算复杂度，避免遍历操作。

2. 一般情况（存在a_i ≠ i）：

采用动态规划思想，利用vector和unordered_set维护GCD集合。通过迭代更新每个位置x的GCD集合，统计集合大小即为答案。具体步骤涉及：

    将a[pos[x]]临时置为1，避免x自身影响；

    遍历数列，动态计算当前元素a[i]与历史GCD的新值，更新集合；

    通过排序与去重确保集合唯一性，最终统计集合大小。

三、解题步骤

1. 输入n及数列a，记录元素位置pos[i]=a[i]的下标；

2. 判断是否为特殊情况（所有a_i=i），若是则调用solve_special_case()；

3. 否则执行一般情况处理：

    初始化GCD集合数组gcd_sets；

    遍历每个x，临时修改a[pos[x]]为1；

    迭代计算新GCD值，更新集合并去重；

    统计集合大小存入ans[x]，恢复a[pos[x]]原值；

4. 输出答案数组ans。

四、代码与注释

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

const int MAXN = 5e5 + 5;  
int a[MAXN], pos[MAXN], ans[MAXN];  

void solve_special_case(int n) {  
    // 当a_i=i时的特殊处理  
    for(int i = 1; i <= n; ++i) {  
        ans[i] = n - (i!= 1);  // 首元素为n，其余为n-1  
    }  
}  

void solve_general_case(int n) {  
    vector<unordered_set<int>> gcd_sets(n + 1);  
    for(int x = 1; x <= n; ++x) {  
        int modified_pos = pos[x];  
        a[modified_pos] = 1;  // 临时修改避免自影响  
        unordered_set<int> S;  
        vector<int> current_gcds;  

        for(int i = 1; i <= n; ++i) {  
            vector<int> new_gcds;  
            int new_gcd = a[i];  
            S.insert(new_gcd);  
            new_gcds.push_back(new_gcd);  

            for(int g : current_gcds) {  
                new_gcd = __gcd(g, a[i]);  
                if(new_gcd!= g || new_gcd == 1) {  
                    S.insert(new_gcd);  
                    new_gcds.push_back(new_gcd);  
                }  
            }  
            current_gcds = new_gcds;  
            sort(current_gcds.begin(), current_gcds.end());  
            current_gcds.erase(unique(current_gcds.begin(), current_gcds.end()), current_gcds.end());  
        }  
        ans[x] = S.size();  
        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;  
        if(a[i]!= i) is_special_case = false;  
    }  

    if(is_special_case) {  
        solve_special_case(n);  
    } else {  
        solve_general_case(n);  
    }  

    for(int i = 1; i <= n; ++i) {  
        cout << ans[i] << " \n"[i == n];  // 优化输出格式  
    }  
    return 0;  
}

五、总结

洛谷P10916题通过巧妙区分特殊与一般情况，结合动态规划与数学优化，实现了高效的答案计算。特殊情况的直接推导显著降低了时间复杂度，而一般情况利用集合维护GCD的动态变化，并通过排序去重保证结果准确性。该题目展现了算法设计中“分类讨论”与“数据结构优化”的重要性，对提升选手逻辑与代码能力具有实践价值。