[BZOJ 3837] Filary

%bill yang

题目大意

给你一坨N个数字, 求最大的pair(A, B)使这N个数字模B意义下有至少一种元素出现超过A次。
B≥1, 保证这N个数字不可能全部相同。

解题报告

非常神奇的题目!

首先如果B取2, 那么答案至少是[latex]\lfloor \frac{N}{2} \rfloor[/latex], 每个数字出现在最优解里的概率至少是二分之一。

随机一个数, 钦定它属于最优解, 把这个数和剩下的数做差, 对每个差值进行质因数分解, 那么出现次数最多的质因数必然可以整除B, 对每个质因数记录一下差值的gcd就可以最大化B了。

随机K次, 那么正确率可以达到[latex]2^{-k}[/latex], 我随机6次wa, 12次ac, 具体看代码。

代码

#include <cstdio>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <set>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long LL;
inline int getInt () {
    int ret; char ch; bool flg = false;
    while((ch = getchar()) < '0' || ch > '9') flg |= (ch == '0');
    ret = ch-'0';
    while((ch = getchar()) >= '0' && ch <= '9') ret = ret*10+(ch - '0');
    return flg ? -ret : ret;
}
const int MAXN = 200010;
const int MAXL = 10000010;
int W[MAXN];
int pre[MAXL];
bool isnprime[MAXL];
int prec[MAXL/6], ptot;
void linerShaker (int lim) {
    int t;
    for(int i = 2; i<=lim; i++) {
        if(!isnprime[i]) prec[++ptot] = i, pre[i] = 1;
        for(int j = 1; j<=ptot && (t=prec[j]*i) <= lim; j++) {
            isnprime[t] = true;
            pre[t] = i;
            if(i%prec[j] == 0) break ;
        }
    }
}
inline int random (int mod) {return rand()%mod;}
int cnt[MAXL], rec[MAXL];
vector<int> prm;
inline int gcd (int a, int b) {
    if(!b) return a;
    return gcd(b, a%b);
}
int main () {
    int N = getInt(), mxv = 0;
    for(int i = 1; i<=N; i++)
        W[i] = getInt(), mxv = max(mxv, W[i]);
    linerShaker(mxv);
    srand(20010627);
    int T = 12;
    int K = -1, M = 0;
    while(T --) {
        int pos = random(N)+1;
        int cur_ans = 0, cur_M = 0, mov = 0;
        prm.clear();
        for(int i = 1; i<=N; i++) {
            if(i == pos) continue ;
            int delta = abs(W[i]-W[pos]);
            if(delta == 0) {
                mov ++;
                continue ;
            }
            int tmp = delta, lst = 0;
            while(tmp != 1) {
                int fac = tmp/pre[tmp];
                if(fac != lst) {
                    lst = fac;
                    if(!cnt[fac]) {
                        prm.push_back(fac);
                        rec[fac] = delta;
                    } else rec[fac] = gcd(rec[fac], delta);
                    cnt[fac] ++;
                    if(cnt[fac] > cur_ans)
                        cur_ans = cnt[fac], cur_M = rec[fac];
                    else if(cnt[fac] == cur_ans)
                        cur_M = max(cur_M, rec[fac]);
                }
                tmp = pre[tmp];
            }
        }
        for(int i = 0; i<(int)prm.size(); i++)
            rec[prm[i]] = cnt[prm[i]] = 0;
        cur_ans += mov+1;
        if(K < cur_ans) K = cur_ans, M = cur_M;
        else if(K == cur_ans) M = max(cur_M, M);
    }
    printf("%d %d\n", K, M);
}