取 (m = 2)，可以得到答案的一个下界是 (lceil {n over 2} ceil)。
直接做很难处理，考虑随机一个值必选。根据答案下界，随机一次能得到最优解的概率大于 (1 over 2)，因此随机 (20) 次左右即可。
同余条件即 (m mid x - y)，(x) 已经通过随机固定，那么枚举每个数 (y)，将 (x - y) 的所有 素因子 用桶维护，取最大值。
但可能存在合数 (m)，使 (k) 同样可以取到最大，可以考虑将两个对应 (a_i) 的位置完全相同 的素因子 “合并”。
如果暴力维护，那么单次尝试 (mathcal O(n log^2 n))，因为合法的素因子只有 (mathcal O(log n)) 个，我们可以考虑给每种 (a_i) 赋随机权值，对每个素因子维护 xor-Hash 即可。
线性筛出每个数最小素因子，复杂度 (mathcal O(V + Tcdot n log n))，(T) 为随机次数。
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <vector>
#include <random>
#include <chrono>
using namespace std;
using ll = long long;
using u64 = unsigned long long;
namespace io {
#define File(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1;
inline char getc () {return (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++);}
inline void flush () {fwrite (obuf, 1, oS - obuf, stdout); oS = obuf;}
inline void putc (char x) {*oS ++ = x; if (oS == oT) flush ();}
template<class T>
inline void read(T &x) {
char ch; int f = 1;
x = 0;
while(isspace(ch = getc()));
if(ch == '-') ch = getc(), f = -1;
do x = x * 10 + ch - '0'; while(isdigit(ch = getc()));
x *= f;
}
template<class T, class ...Args>
inline void read(T &x, Args&... args) {read(x); read(args...);}
template<class T>
inline void write(T x) {
static char stk[128];
int top = 0;
if(x == 0) {putc('0'); return;}
if(x < 0) putc('-'), x = -x;
while(x) stk[top++] = x % 10, x /= 10;
while(top) putc(stk[--top] + '0');
}
template<class T, class ...Args>
inline void write(T x, Args... args) {write(x); putc(' '); write(args...);}
inline void space() {putc(' ');}
inline void endl() {putc('
');}
struct _flush {~_flush() {flush();}} __flush;
};
using io::read; using io::write; using io::flush; using io::space; using io::endl; using io::getc; using io::putc;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int V = 10000004, P = 664600, N = 1000005;
bool np[V];
int p[P], pc = 0, lpf[V];
void prime_sieve(int n) {
for (int i = 2; i <= n; ++i) {
if (!np[i])
p[++pc] = i, lpf[i] = pc;
for (int j = 1; j <= pc && i * p[j] <= n; ++j) {
np[i * p[j]] = true;
lpf[i * p[j]] = j;
if (i % p[j] == 0) break;
}
}
}
int k = 0, m = -1;
int cnt[N], val[N], minexp[N], cv = 0;
u64 id[N], Hash[P];
int occ[P];
void work(int select) {
fill(Hash + 1, Hash + 1 + pc, 0);
fill(occ + 1, occ + 1 + pc, 0);
fill(minexp, minexp + 1 + pc, numeric_limits<int>::max());
int nowc = 0;
for (int i = 1; i <= cv; ++i) {
if (val[i] == select) {
nowc = cnt[i];
continue;
}
int x = abs(val[i] - select);
int last = 0, ex = 0;
while (x != 1) {
if (lpf[x] != last) {
occ[lpf[x]] += cnt[i];
if (last) minexp[last] = min(minexp[last], ex);
ex = 1;
Hash[lpf[x]] ^= id[i];
last = lpf[x];
}
else ++ex;
x /= p[lpf[x]];
}
if (last) minexp[last] = min(minexp[last], ex);
}
int K = *max_element(occ + 1, occ + 1 + pc), M = 0, fc = 0;
static int fac[128], prod[128];
if (K + nowc < k) return;
for (int i = 1; i <= pc; ++i)
if (occ[i] == K) fac[++fc] = i;
for (int i = 1; i <= fc; ++i) {
prod[i] = 1;
for (int t = minexp[fac[i]]; t; --t) prod[i] *= p[fac[i]];
for (int j = 1; j < i; ++j)
if (Hash[fac[i]] == Hash[fac[j]]) {
prod[j] *= prod[i];
break;
}
}
K += nowc;
M = *max_element(prod + 1, prod + 1 + fc);
if (K > k) m = M, k = K;
else if (K == k && M > m) m = M;
}
int a[N];
int main() {
prime_sieve(10000000);
int n, cmod2[2] = {0, 0};
read(n);
m = 2;
for (int i = 1; i <= n; ++i)
read(a[i]), ++cmod2[a[i] & 1];
k = max(cmod2[0], cmod2[1]);
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; ++i) {
if (a[i] != a[i - 1]) {
++cv;
val[cv] = a[i]; cnt[cv] = 1;
id[cv] = rnd();
}
else ++cnt[cv];
}
uniform_int_distribution<int> D(1, n);
for (int T = 1; T <= 20; ++T) {
int p = D(rnd);
work(a[p]);
}
write(k, m), endl();
return 0;
}