CF1855B Longest Divisors Interval 题解

Iniaugoty · 2023-07-30 13:11:56 · 题解

problem

求出一个区间，使其中所有整数都是 n 的因数，最大化区间长度。

solution

由容斥原理和模运算的一些性质，易知，[l,r] 都整除 n 是 [1,r-l+1] 都整除 n 的充分不必要条件。证明略。

因此，贪心地从 1 开始枚举一段连续的整除 n 的数即可。

code

std::cin >> n;
int ans = 0;
while (n % ++ans == 0);
std::cout << ans - 1 << "\n";