AtCoder ABC #272 : G - Yet Another mod M

Gまではいいんだけどね…。
https://atcoder.jp/contests/abc272/tasks/abc272_g

問題

整数列Aが与えられる。
ある3以上の整数Mを選び、A[i]をA[i] % Mで置き換えたとき、A中である値が過半数を占めるようにしたい。
それが可能か判定し、可能なら1つMを求めよ。

解法

乱択で解くことを考える。

A[i] % MとA[j] % Mがともに過半数側に含まれると仮定する。
(i,j)をランダムに500回ほど選び、A[i]%M=A[j]%Mとなる3以上のMを列挙して、実際にそのMによりある値が過半数を占めるか試せばよい。

もし解となるMが存在するなら、(i,j)の対は1/4程度の確率でA[i]%MとA[j]%Mがその過半数に含まれることになるので、500組ほど試せばほぼ確実に判定できる。

int N;
ll A[5050];
map<int,int> Ms;

map<ll,int> enumpr(ll n) {
	map<ll,int> V;
	for(ll i=2;i*i<=n;i++) while(n%i==0) V[i]++,n/=i;
	if(n>1) V[n]++;
	return V;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	
	srand(time(NULL));
	FOR(i,500) {
		x=rand()%N;
		y=rand()%N;
		while(y==x) y=(y+1)%N;
		map<ll,int> m=enumpr(abs(A[x]-A[y]));
		FORR2(a,b,m) {
			if(a==2&&b==1) continue;
			int v;
			if(a==2) v=4;
			else v=a;
			Ms.clear();
			FOR(j,N) {
				Ms[A[j]%v]++;
				if(Ms[A[j]%v]+Ms[A[j]%v]>N) {
					cout<<v<<endl;
					return;
				}
			}
		}
		
	}
	cout<<-1<<endl;
	
	
}

まとめ

ABCで乱択出たの久しぶりだったりする？