Codeforces #511 Div1 A. Enlarge GCD

イマイチな出来だった回。
http://codeforces.com/contest/1034/problem/A

問題

N個の整数A[i]が与えられる。
いくつかの要素を削除し、削除後のGCDが削除前のGCDを上回るようにしたい。
最小何個の要素を削除すればよいか。

解法

全要素等しい場合は何もできない。
そうでない場合、元のGCDをGとする。
各要素に対し整数A[i]/Gを素因数分解し、各素数の登場回数を求めよう。
登場回数が最多の素数に対応する要素を残すようにすればよい。

const int prime_max = 1000000;
int NP,prime[100000],divp[prime_max];

void cprime() {
	if(NP) return;
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		//M[i]=NP;
		prime[NP++]=i;
		for(ll j=1LL*i*i;j>=i&&j<prime_max;j+=i) if(divp[j]==0) divp[j]=i;
	}
}

int N;
int A[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cprime();
	
	cin>>N;
	int g=0;
	FOR(i,N) {
		cin>>A[i];
		g=__gcd(g,A[i]);
	}
	FOR(i,N-1) if(A[i]!=A[i+1]) break;
	if(i==N-1) return _P("-1\n");
	
	
	map<int,int> M;
	FOR(i,N) {
		x=A[i]/g;
		for(j=0;prime[j]*prime[j]<=x;j++) {
			if(x%prime[j]==0) {
				M[prime[j]]++;
				while(x%prime[j]==0) x/=prime[j];
			}
		}
		if(x>1) M[x]++;
	}
	
	int ma=0;
	FORR(m,M) ma=max(ma,m.second);
	cout<<N-ma<<endl;
	
	
	
}

まとめ

ここまでは良かったんだけどね。