题解 CF1855B Longest Divisors Interval
W_s_W
·
·
题解
更新：
- 2023/7/31：该题解已审核通过，但表格存在格式错误，现已修改，麻烦重新审核。
思路：
从 1 开始枚举，每次答案加一，找到第一个不是 n 的因数的数退出枚举，输出答案。
证明：
观察能整除 3 的数的出现规律：
| 数字 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
| 能否整除 3 |
✗ |
✗ |
✓ |
✗ |
✗ |
✓ |
✗ |
✗ |
✓ |
✗ |
✗ |
✓ |
显而易见，能否整除数字 p 的规律是（从 1 开始）：
$p-1$ 个数不能整除 $p$，第 $2p$ 个数字可以整除 $p$。
根据上述循环，我们可以得出结论：
在长度为 $p$ 的连续整数列中，必定存在一个数 $k$，使得 $p\mid k$。
回到题目中，假设正确答案为 $x$，且存在一个符合题意的区间 $[l,r]$，使得 $l\ne1,r-l+1=x$。
根据上面的结论：在长度为 $x$ 的连续整数列中，必定存在一个数 $k$，使得 $x\mid k$。简单来说就是区间 $[l,r]$ 内肯定有一个数能够整除 $x$。
同理，区间 $[l,r-1]$ 内肯定有一个数能够整除 $x-1$。
继续延展，得出：区间 $[l,r]$ 内肯定存在**某个**整数，能够整除 $[1,x]$ 的任意一个整数。
因为区间 $[l,r]$ 内的任意一个整数都能被 $n$ 整除，所以区间 $[1,x]$ 内的任意一个整数也都能被 $n$ 整除。
综上所述，符合题意的所有区间中，肯定存在区间 $[1,x]$。
---
### 代码和[提交记录](https://codeforces.com/contest/1855/submission/216275689)
```cpp
#include<bits/stdc++.h>
using namespace std;
int t;
long long n;
long long cnt;
int main(){
scanf("%d",&t);
while(t--){
scanf("%lld",&n);
cnt=0;
if(n&1){
puts("1");
continue;
}
for(int i=1;n%i==0;i++)cnt++;
printf("%lld\n",cnt);
}
return 0;
}
```