%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); }
Join the discussion