题解
2025-02-10 11:07:44
发布于:广东
22阅读
0回复
0点赞
显然当 时有最长的区间。这里我给出证明。
设 最小的不能整除的正整数为 。
当 能整除一个数时,它一定能整除这个数的所有的因子,
又 每相邻 个数内必定有一个数是 的倍数(对 取余可知),
最长的区间长度一定不超过 。
那么,我们能不能构造一个长度为 的区间呢?
显然 就是一个合法的区间。
故答案为 。
#include <iostream>
#include <cstdio>
using namespace std;
void solve(){
long long n, i = 1;
cin >> n;
for(; n % i == 0; i++);
cout << i - 1 << '\n';
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t--) solve();
return 0;
}
时间复杂度:。
这里空空如也
有帮助,赞一个