千鸽笼 题解

日常竞赛测试讨论
1

题目链接：problem

题意：

有 A~B 这 (B-A+1) 个数，现在要将这几个数合并几组，要求组的所有数的公共质因数不小于 p ，求最少能分几组

很好的题，提示了要用并查集

(并查集模板：

void init () {
	for (int i = 1 ; i <= B ; i ++)  f [i] = i ;
}
int find (int x) {
	return f [x] == x ? x : f [x] = find (f [x]) ;
}
void merge (int x , int y) {
	int fx , fy ;
	fx = find (x) ; fy = find (y) ;
	if (fx != fy)  f [fx] = fy ;
}

)

那么想想：只要选定一个公共质因数 x ，保证 x >= p ， 那么将它的倍数都合并，就行了。

for (int i = 2 ; i <= B ; i ++)
		if (! prime [i] && i >= k) {
			sum = 0 ; 
			for (int j = 1 ; j <= B / i ; j ++)
				if (i * j >= A) {
					sum ++ ; 
					if (sum == 1)  p = i * j ;
					else  merge (p , i * j) ;  //merge
				}
		}

最后在计数一下(我喜欢用map，因为map能放一存一，唯一缺点速度较慢)
输出答案

1 个赞