1855B.Longest Divisors Interval

Description:

• 对于一个整数 \(n\) \((1\leq n \leq 10^{18})\)，找到一段最长的区间\([l,r]\)，使得区间内所有数均为 \(n\) 的约数。

Analysis:

• 如果 \(n\)是一个奇数（非 \(2\)的倍数），由于 \(odd = odd \times odd\)，则不可能有连续的两个整数均为 \(n\) 的约数；
• 推广：连续3个整数中必有一个是3的倍数，连续x个整数中必有x的倍数
• 若区间 \([l,r]\) 成立，则区间 \([1,r-l+1]\) 也成立（可以通过取模运算转化），故只需从1开始找到第一个（最小的）\(x\) (\(x\)不是\(n\)的约数)，则 \(ans = x-1\)
• （补充）关于枚举边界的确定：由唯一分解定理 \(n=p_1^{\alpha_1}p_2^{\alpha_2}···p_k^{\alpha_k}\)，可对 \(1e18\) 粗略考虑，已知在 \(\alpha_1=\alpha_2=···=\alpha_k=1\) 的条件下，连续质数相乘：\(p_k=47\)时，\(n\approx6e17\)；\(p_k=53,n\approx1e19\)。故在\(\alpha\geq1\)时，\(53\) 即为可行的枚举边界。

// 边界验证
init(); //初始化素数筛
ull res = 1;
for(int i=1;i<=53;i++) {
	if(prime[i]) {
		res *= i;
		cout << "素数:" << i << " " << "res: " << res << endl;
	}
}
素数:2 res: 2
素数:3 res: 6
素数:5 res: 30
素数:7 res: 210
素数:11 res: 2310
素数:13 res: 30030
素数:17 res: 510510
素数:19 res: 9699690
素数:23 res: 223092870
素数:29 res: 6469693230
素数:31 res: 200560490130
素数:37 res: 7420738134810
素数:41 res: 304250263527210
素数:43 res: 13082761331670030
素数:47 res: 614889782588491410
素数:53 res: 14142414403480493114

Solution:

void solve() {
	ll n; cin >> n;
	for(int i=1;i<=55;i++) {
		if(n % i != 0) {
			cout << i-1 << endl;
			return ;
		}
	}
}