给定一组n个正整数,要求每次选其中一个数乘以或除以一个素数(称为一次凑数),问至少需要凑数多少次可以把所有的数都凑成相等。
时间: 2024-04-21 14:29:16 浏览: 21
这是一个非常经典的数学问题,可以用数学归纳法来解决。首先,如果只有两个数a和b,那么最少需要凑数的次数就是它们之间的差值的因子个数,因为每次凑数只能改变一个数的值,所以需要凑数的次数就等于它们之间的差值的因子个数。
接下来考虑对于n个数的情况。我们可以先对n个数求出它们的最大公约数g,然后将它们都除以g,这样它们就都凑成了一样的数,而且它们的最大公约数为1。
现在我们要将它们凑成相等的数,假设它们都等于k,那么我们需要将每个数a[i]都凑成k。我们可以把k分解质因数,得到k=p1^a1 * p2^a2 * ... * pn^an,其中p1、p2、...、pn都是不同的素数。由于每次凑数只能乘以或除以一个素数,那么对于每个素数pi,我们需要将所有的a[i]都凑成pi^x的形式,其中x是一个整数。
对于任意一个素数pi,我们可以将所有的a[i]对pi取模,得到一组余数r[1]、r[2]、...、r[n],其中0 <= r[i] <= pi-1。如果这些余数中有一个数不为0,那么我们就必须将这个数凑成0,需要至少一次凑数。如果这些余数都为0,那么我们就不需要凑数了,因为a[i]都能被pi整除。
因此,对于每个素数pi,我们需要将所有的余数都凑成0。这样,我们可以将所有的余数分成若干组,其中每组的余数都是pi的倍数,然后对于每组余数,我们可以用相同的方法来计算需要凑数的次数。最终,所有素数的凑数次数之和就是我们要求的答案。
需要注意的是,我们需要用到一个定理,即对于任意一个正整数n,它的质因数分解中最多只有log2(n)个质因数。因此,在实际计算中,我们只需要枚举不超过log2(max(a[i]))的素数即可。