传送门
这题真有意思。题目还特意说了是最近一场cf的加强版，结果跟cf那道题的做法几乎是完全不一样，竟然用随机过掉了。
先说一下cf那道题的题意：给一个长度为(n)的序列(a)，让你选择一个最长的子区间([l,r])，满足(exists m)，使得所有(a_i in [l,r])在( extrm{mod} m)意义下同余，输出最长子区间长度。
对于这道题，我们只要预处理出差分数组，然后选择最长的区间，满足该区间内的最大公约数大于(1)即可。我当时用st表预处理+二分写的。
而今天的比赛题，将子区间改成了子序列。
这就大有不同了，首先应该发现的是，答案必然大于等于(lceil frac{n}{2} ceil)，即当(m=2)时的答案。
这一点，为接下来的随机化算法提供了理论依据：我们随机两个位置(x,y)，那么(a_x,a_y)都在答案中的最长子序列的概率必然不小于(frac1{4}).如果随机(K)次并取每一次的最大值，那么失误的概率就是((frac{3}{4})^K)，当(K=30)的时候就是(10^{-3})级别了，可几乎认为是正确的了。
因此我们随机(K)次，然后每次随机，用(|a_x-a_y|)的所有质因子作为模数去求最长子序列长度，这样时间复杂度就是(O(Kp(sqrt{ extrm{max} a_i})+11nK))，其中(p(n))表示(n)以内的质数个数，是(O(frac{n}{log n}))级别，(11)是(4*10^{12})以内不同的质数的个数。
#include<bits/stdc++.h>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define In inline
typedef long long ll;
typedef double db;
const int maxn = 3e6 + 5;
const int K = 30;
In ll read()
{
ll ans = 0;
char ch = getchar(), las = ' ';
while(!isdigit(ch)) las = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(las == '-') ans = -ans;
return ans;
}
In void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
int n;
ll a[maxn];
bool vis[maxn];
int p[maxn], pcnt = 0;
In void init()
{
for(int i = 2; i < maxn; ++i) if(!vis[i])
{
p[++pcnt] = i;
for(int j = i; 1LL * j * i < maxn; ++j) vis[j * i] = 1;
}
}
In int check(ll p, ll r)
{
int cnt = 0;
for(int i = 1; i <= n; ++i) cnt += (a[i] % p == r);
return cnt;
}
In int solve()
{
int ret = 1;
for(int k = 1; k <= K; ++k)
{
int x = rand() % n + 1, y = rand() % n + 1;
while(x == y) x = rand() % n + 1, y = rand() % n + 1;
ll tp = abs(a[x] - a[y]);
for(int i = 1; 1LL * p[i] * p[i] <= tp; ++i)
{
if(tp % p[i] == 0)
{
ret = max(ret, check(p[i], a[x] % p[i]));
while(tp % p[i] == 0) tp /= p[i];
}
}
if(tp > 1) ret = max(ret, check(tp, a[x] % tp));
}
return ret;
}
int main()
{
srand(time(0));
init();
int T = read();
while(T--)
{
n = read();
for(int i = 1; i <= n; ++i) a[i] = read();
write(solve()), enter;
}
return 0;
}