Google Code Jam 2008 Round 1B : B. Number Sets

さて２問目。
http://code.google.com/codejam/contest/32017/dashboard#s=p1

最大100万までの差がある整数A,Bと、B以下の整数Pが与えられる。
A～Bまでの整数をグループ分けする際、グループ間で１組でもP以上の素数を共通因数とする整数があれば、そのグループはマージされる。
このときA～Bは何個のグループにまとまるかを答える。

グループのマージなので、これはあからさまにUnion-Findを使う問題。
A～Bの差は100万なので、最初にP～100万までの素数を求めておき、その各素数に対して、A～B間の倍数をunionしていく。
各素数P'ごとに100万/P'個のunion処理をするので、O(NlogN)位かな？

int np;
s64 prime[100000];
const int prime_max = 1000000;
void cprime() {
	int i,j;
	char p[prime_max];
	
	np=0;
	ZERO(p);
	for(i=2;i<prime_max;i++) {
		if(p[i]) continue;
		prime[np++]=i;
		for(j=i*2;j<prime_max;j+=i) p[j]=1;
	}
}

s64 A,B,P;
s64 num[9];

const int ufmax=1000001;
int ufpar[ufmax];
int ufrank[ufmax];
int UF_init(){
	int i;
	FOR(i,ufmax) ufpar[i]=i;
	FOR(i,ufmax) ufrank[i]=0;
}
int UF_find(int x) {
	return (ufpar[x]==x)?(x):(ufpar[x] = UF_find(ufpar[x]));
}
void UF_unite(int x,int y) {
	x = UF_find(x); y = UF_find(y);
	if(x==y) return;
	if(ufrank[x]<ufrank[y]) ufpar[x]=y;
	else {ufpar[y]=x; if(ufrank[x]==ufrank[y]) ufrank[x]++;}
}


void solve(int _loop) {
	int i,j,k,l;
	s64 res;
	s64 ii,t;
	
	scanf("%lld%lld%lld%",&A,&B,&P);
	UF_init();
	
	FOR(i,np) {
		s64 p=prime[i];
		if(p<P || p>B-A) continue;
		for(t = ((A+(p-1))/p)*p; t<=B; t+=p) {
			UF_unite(((A+(p-1))/p)*p-A,t-A);
		}
	}
	res=0;
	for(ii=A;ii<=B;ii++) if(UF_find(ii-A)==ii-A) res++;
	
	_PE("Case #%d: %lld\n",_loop,res);
}

void init() {
	cprime();
}

まとめ

Union-findの典型的な問題。
Union-findの練習にいいね。