CF1855B Longest Divisors Interval 题解

原题链接：https://codeforces.com/contest/1855/problem/B

题意：给定一个正整数 n, 找到满足该条件的区间 [l, r] 的长度的最大值：对于任意 l <= i <= r，n 均为 i 的倍数（多组数据）。

思路：如果 n 是奇数，答案显然是 1，因为任意两个连续的正整数一定会有一个 2 的倍数。将这一结论进行推广：如果 n 是偶数，但不是 3 的倍数，答案就是 2，因为任意三个连续的正整数一定会包含 3 的倍数；如果 n 既是偶数，也是 3 的倍数，但不是 4 的倍数，那么答案就是 3……

综上，只要从 1 开始枚举，找到第一个不是 n 的约数的正整数即可。

证明这样做不会超时：设 1, 2, ..., x 都是 n 的约数，那么 lcm(...lcm(lcm(lcm(1, 2), 3), 4)..., x) 一定也是 n 的约数，当 x = 44 时，这个值已经超过了 1e18。

#include <iostream>

void solve() {
    long long n;
    std::cin >> n;
    for (long long i = 1; true; ++i) {
        if (n % i != 0) {
            std::cout << i - 1 << "\n";
            return;
        }
    }
}

int main() {
    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}