Longest Divisors Interval

题面翻译

给出一个正整数 $n$，求出一个区间 $[l, r]$ 使得区间内的每一个整数都是 $n$ 的因数且该区间的大小最大。输出这个区间的大小。

多测。数据范围：$1 \le n \le 10^{18}$，$1 \le t \le 10^4$。

题目描述

Given a positive integer $ n $ , find the maximum size of an interval $ [l, r] $ of positive integers such that, for every $ i $ in the interval (i.e., $ l \leq i \leq r $ ), $ n $ is a multiple of $ i $ .

Given two integers $ l\le r $ , the size of the interval $ [l, r] $ is $ r-l+1 $ (i.e., it coincides with the number of integers belonging to the interval).

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases.

The only line of the description of each test case contains one integer $ n $ ( $ 1 \leq n \leq 10^{18} $ ).

输出格式

For each test case, print a single integer: the maximum size of a valid interval.

样例 #1

样例输入 #1

10
1
40
990990
4204474560
169958913706572972
365988220345828080
387701719537826430
620196883578129853
864802341280805662
1000000000000000000

样例输出 #1

1
2
3
6
4
22
3
1
2
2

提示

In the first test case, a valid interval with maximum size is $ [1, 1] $ (it’s valid because $ n = 1 $ is a multiple of $ 1 $ ) and its size is $ 1 $ .

In the second test case, a valid interval with maximum size is $ [4, 5] $ (it’s valid because $ n = 40 $ is a multiple of $ 4 $ and $ 5 $ ) and its size is $ 2 $ .

In the third test case, a valid interval with maximum size is $ [9, 11] $ .

In the fourth test case, a valid interval with maximum size is $ [8, 13] $ .

In the seventh test case, a valid interval with maximum size is $ [327869, 327871] $ .

第一：奇数的约数没有偶数，如果区间长度大于等于2，那么必然会有偶数，所以n如果是奇数，长度必然是1

第二：如果连续整数区间[l,r]大于等于x，那么这个区间必然会有x的整数，我们选择[1,x]这个区间，其中x为从1开始的第一个不是n的因数的数的前一个数。我们可以证明到不会有比这个区间更优秀的区间。

证明：假设[l,r]更优，长度必然大于等于x+1，我们说了x+1不是n的约束，所以[l,r]不可能比[1,x]更优

这种题可以打表找规律

const int N = 2e5 + 10;
int a[N];
void solve()
{
    int n;
    cin >> n;
    int ok = 1;
    while (n%ok == 0)
    {
        ok++;
    }
    cout << ok - 1 << '\n';
}