526互联

* Codeforces Round 889 (Div. 2) B. Longest Divisors Interval

发布时间 2023-09-05 21:22:53作者: zsxuan

给一个正整数 \(n\) ，找一段最长的 \([l, r]\) ，满足 \(\forall i, i \in [l, r],\ s.t.\ i | n\) 。输出这一段区间的长度，即 \(r - l + 1\) 。

这题是一个准结论题，需要一些知识点和观察的基础。

放在 \(900\) 的位置是因为结论存在的区间太容易枚举出来了。

观察一：连续段整除问题，必然用到性质：

  • 定理：连续 \(x\) 个数有且仅有在一个数被 \(x\) 整除。
    • 证明：对于一段连续段 \([l, r]\) ，在 \(\mod (r - l + 1)\) 意义下，取遍所有余数 \([0, r - l]\) 。余数 \(0\) 存在且仅存在一个。
  • 推论：对任意 \([l, r]\) ，若 \(\exists i, i \in [l, r]\) ，满足 \(\forall j, j \in [1, r - l + 1]\) ，有 \(j | i\) 。直接使用上述定理可以归纳证明。

观察二：当存在 \([l, r] | n\) ，则有 \([1, r - l + 1] | n\) 。则最长的 \([l, r] | n\) ，有最长的 \([1, r - l + 1] | n\) 。

于是问题可以求解。从 \(1\) 开始找连续的 \(x\) 满足 \(x | n\) ，\(x_{max}\) 即最长连续段整除 \(n\) 的段长。

view 
#include <bits/stdc++.h>
typedef long long ll;
void solve() {
	ll n; std::cin >> n;
	for (int x = 1; ; x++) if (n % x != 0) { std::cout << x - 1 << '\n'; return; }
}
signed main() {
	int _ = 1; std::cin >> _;
	while (_--) { solve(); }
	return 0;
}