CF杂题选刷

CF1855B Longest Divisors Interval

对于任意一个区间 \(\left[ l,r \right]\)，一定有 \(\forall i \in \left[ 1,r-l+1 \right]\)，都 \(\exists j \in \left[ l,r \right]\)，使得 \(i \mid j\)。

因为模 \(i\) 意义下的正整数每 \(i\) 个一循环，由于 \(i\) 小于区间长度，所以在这个区间内一定存在至少一个 \(0\)。

所以对于区间 \(\left[ l,r \right]\)，若 \(\forall i \in \left[ l,r \right]\) 都满足 \(i \mid n\)，那么对于 \(\forall i \in \left[ 1,r-l+1 \right]\) 也一定满足 \(i \mid n\)。

所以对于 \(\forall i \in \left[ 1,r-l+1 \right]\)，都能在 \(\left[ l,r \right]\) 中找到 \(i\) 的倍数。

所以问题就转化为从 \(1\) 开始枚举，找到 \(r-l+1\) 合法的最大值。

int ans = 1;
    for(int i = 1;  ; i++) {
        if(n % i != 0) {
            ans = i - 1;
            break;
        }
    }