CF125 Div.1 经典基础题，Petya and Divisors——数论结合滑动窗口

Codeforces（简称CF）早期的Div.1+Div.2或单独Div.1/2的短编号Round（如Round #125）常能找到兼顾思维深度与实现简洁性的入门级难题，其中CF125 Div.1 B题（对应旧Div.2 Round #200 F？不，需注意短编号Round单独算，本题全称为Codeforces Round #125 (Div. 1 Only) Problem B）「Petya and Divisors」 就是一道非常适合数论初学者结合滑动窗口巩固知识点的题目——它既不涉及复杂的筛法优化（基础素数筛即可辅助预处理），也没有绕弯的数学推导，但要求对「维护出现过的约数与窗口右边界的关系」有清晰的思路。

回顾先快速梳理一下原题题意（避免混淆编号错误，这里以经典公开版本为准）：

给定长度为 ( n ) 的正整数数组 ( a_1, a_2, \dots, a_n )，对于每个位置 ( i )（( 1 \leq i \leq n )），求更大的整数 ( L_i ),满足以下条件：

区间 ([L_i, i]) 内的所有元素 ( a_j )（( L_i \leq j \leq i )）都能被某个正整数 ( d ) 整除；

这个 ( d ) 不能整除数组中位置在 ( [1, L_i-1] ) 的任何元素（也就是 ( d ) 是区间 ([L_i, i]) 内独有的「公共约数候选」的更大可能支撑区间的左端点？更通俗的说法：在所有可能的、「能整除当前元素 ( a_i ) 且之前最后一次出现的位置 < 当前遍历位置」的约数中，取最后一次出现位置的更大值，这个更大值就是 ( L_i )，最后输出 ( i - L_i )）。

核心思路解析

简化问题的之一步：找到每个 ( d ) 的「有效出现范围」

我们可以换个角度思考问题：对于数组中的任意正整数约数 ( d )，假设它在数组中最后一次出现在位置 ( last[d] )（初始时所有 ( last[d] = 0 )），当我们遍历到第 ( i ) 个元素时，所有能整除 ( a_i ) 的约数 ( d )，它们现在的有效支撑区间的左边界下限就变成了 ( last[d] + 1 )——因为要保证 ( d ) 不在 ( [1, L_i-1] ) 里出现。

第二步：滑动窗口的核心——取所有下限的更大值

对于第 ( i ) 个位置，我们需要找的 ( L_i ) 是所有能整除 ( a_i ) 的约数 ( d ) 对应的 ( last[d] + 1 ) 的更大值，为什么？因为只有当左边界取到所有约数的左边界下限中更大的那个时，才能同时满足「所有区间内元素有共同约数」（这个共同约数必然是 ( a_i ) 的某个约数，因为 ( a_i ) 在区间里）和「这个共同约数不在区间外左边出现」（所有候选约数的下限都被覆盖了，更大的那个决定了最终的左边界）。

第三步：预处理约数还是现场枚举？

对于 ( a_i ) 的范围，经典版本中一般是 ( 1 \leq a_i \leq 10^6 )——这个范围用「预处理每个数的所有约数」的 *** 是完全可行的，时间复杂度为 ( O(M \log M) )（( M = 10^6 )），比现场枚举每个 ( a_i ) 的平方根找约数（单次 ( O(\sqrt{M}) )，总 ( O(n \sqrt{M}) )）更高效，尤其是当 ( n ) 比较大的时候。

具体实现步骤

预处理约数数组：定义一个二维数组（或vector的vector）divisors，divisors[x] 存储 ( x ) 的所有正约数，初始化时，从 ( 1 ) 到 ( M ) 遍历每个数 ( d )，再把 ( d ) 加入到 divisors[k*d] 中（( k*d \leq M )）。
初始化最后出现位置数组：定义一个数组 last，长度为 ( M+1 )，初始值全部设为 ( 0 )。
遍历数组计算答案：
- 定义当前窗口的左边界 ( current_L = 0 )；
- 对于每个 ( i ) 从 ( 1 ) 到 ( n )：
  - 取出 ( a_i ) 的所有约数 divisors[a_i]；
  - 遍历这些约数 ( d )，更新 current_L 为 max(current_L, last[d] + 1)；
  - 再次遍历这些约数 ( d )，更新 last[d] 为 ( i )（因为现在 ( d ) 最后一次出现在 ( i ) 了）；
  - 输出 ( i - current_L )。

代码示例（C++）

#include <iostream>
#include <vector>
using namespace std;
const int MAX_A = 1e6 + 5;
vector<int> divisors[MAX_A];
void precompute_divisors() {
    for (int d = 1; d < MAX_A; d++) {
        for (int multiple = d; multiple < MAX_A; multiple += d) {
            divisors[multiple].push_back(d);
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    precompute_divisors();
    int n;
    cin >> n;
    vector<int> a(n + 1); // 下标从1开始更方便
    vector<int> last(MAX_A, 0);
    int current_L = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        // 之一步：遍历a[i]的所有约数，找到更大的last[d]+1作为current_L
        for (int d : divisors[a[i]]) {
            if (last[d] + 1 > current_L) {
                current_L = last[d] + 1;
            }
        }
        // 第二步：更新所有约数的last[d]为i
        for (int d : divisors[a[i]]) {
            last[d] = i;
        }
        // 输出答案
        cout << i - current_L << '\n';
    }
    return 0;
}

复杂度分析

时间复杂度：预处理约数 ( O(M \log M) )（( M = 10^6 ) 时约为 ( 10^7 ) 次操作，完全可以通过），遍历数组时每个约数最多被处理两次（一次更新左边界，一次更新最后出现位置），总约数个数约为 ( O(n \log M) )，因此总时间复杂度为 ( O(M \log M + n \log M) )。
空间复杂度：预处理约数数组约为 ( O(M \log M) )，last 数组为 ( O(M) )，数组 a 为 ( O(n) )，总空间复杂度在 ( 10^6 ) 范围内是完全可以接受的。

CF125 Div.1 B题「Petya and Divisors」的巧妙之处在于将公共约数的问题转化为了「维护约数最后出现位置」的滑动窗口问题——不需要去枚举所有可能的公共约数，只需要利用「当前元素的约数是所有包含当前元素的公共约数区间的必要候选」这一性质，就能高效地找到每个位置的最长有效区间，这道题不仅能巩固约数的预处理，还能加深对滑动窗口「维护关键状态」这一核心思想的理解，是一道非常优质的入门级数论+滑动窗口题目。

正文