質因數分解應用

• 2020 年 12 月 19 日
• 筆記
• 素數篩

題目大意

給定 \(n\) 個數字，將這 \(n\) 個數字乘起來。找到 \(1\) 個數字 \(k\) ，使得 \(k!\) 能被 \(n\) 整除。求最小的 \(k\) 。

思路

先將 \(n\) 個數字分別質因數分解，用桶 \(B1\) 把這些質因數的個數統計起來。

按照題目的意思，需要找到一個 \(k!\) ，將其質因數分解，也把分解的這些質因數裝進另一個桶 \(B2\) 里，使得桶 \(B2\) 里所有元素的個數都大於桶 \(B1\) 裏面所有元素的個數。

怎麼來找這個桶呢？可以二分枚舉，找出答案。

這裡分享另一種做法。

對於桶裏面的每一個元素，都可以找到 \(1\) 個最小滿足含有這個元素的乘積的倍數。描述有一些模糊，舉個例子：

有 \(2\) 個數字，\(81\) 和 \(45\)。將這兩個數字分解，則桶 \(B1\) 里，\(3\) 的個數為 \(6\) ，\(5\) 的個數為 \(1\) 。則最小滿足 \(6\) 個 \(3\) 的數字為 \(15\)。其中， \(3\) 做 \(1\) 個貢獻， \(6\) 做 \(1\) 個貢獻， \(9\) 做 \(2\) 個貢獻， \(12\) 做 \(1\) 個貢獻， \(15\) 做 \(1\) 個貢獻。簡單來說，這個數字含有多少個 \(3\) ，就做多少貢獻。可以直接暴力枚舉，枚舉到滿足條件即可，這個數據枚舉到 \(15\) 。對於 \(5\) 同理，枚舉到 \(5\) 即可。最後取這兩個數的最大值，因為 \(15!\) 就包含了 \(5!\) ，而且兩質數之間互不干擾，沒有交集。故而答案為 \(15\)。

總結

先用桶存儲這 \(n\) 個數字的質因數個數，找桶中每個元素，滿足這個元素的最小的 \(k\) ，取最大值來滿足條件即可。

C++代碼

#include <cstdio>
#define Max(a, b) ((a) > (b) ? (a) : (b))
void Quick_Read(int &N) {
	N = 0;
	int op = 1;
	char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-')
			op = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9') {
		N = (N << 1) + (N << 3) + (c ^ 48);
		c = getchar();
	}
	N *= op;
}
const int MAXN = 1e5 + 5;
int bucket[MAXN];
bool flag[MAXN], vis[MAXN];
int p[MAXN];
int n, cnt, num;
void Primes() {
	int k = 100000;
	flag[1] = 1;
	for(int i = 2; i <= k; i++) {
		if(!flag[i])
			p[++cnt] = i;
		for(int j = 1; p[j] * i <= k && j <= cnt; j++) {
			flag[p[j] * i] = true;
			if(i % p[j] == 0)
				break;
		}
	}
}
int main() {
	int A;
	Primes();
	Quick_Read(n);
	for(int i = 1; i <= n; i++) {
		Quick_Read(A);
		for(int j = 1; j <= cnt && A != 1; j++) {
			if(A <= 100000 && !flag[A])
				break;
			while(A % p[j] == 0) {
				A /= p[j];
				bucket[p[j]]++;
				if(!vis[p[j]])
					num++;
				vis[p[j]] = true;
			}
		}
		if(!vis[A] && A != 1)
			num++;
		vis[A] = true;
		bucket[A]++;
	}
	int ans = 0;
	for(int i = 2; i <= 100000; i++) {
		if(!bucket[i])
			continue;
		int j = 0, product, maxn = 0;
		while(bucket[i] > 0) {
			j++;
			product = j * i;
			while(product % i == 0) {
				product /= i;
				bucket[i]--;
			}
			maxn++;
		}
		ans = Max(ans, maxn * i);
	}
	printf("%d", ans);
	return 0;
}