鉴于阵列A1,A2。 。 。 AN是什么阵列这样的最大子集的每对元件中的子集是互质的大小。
Given an array A1, A2 . . . AN what is the size of the largest subset of the array such that the each pair of elements in the subset is coprime.
实施例:设N = 5和阵列是[2 3 2 3 2],然后回答是2
Example : Let N=5 and array be [2 3 2 3 2] then answer is 2
说明:最大的子集将采取之一的[0],A [1],A [2],并采取之一的[3],A [4]
Explanation : The largest subset would be taking one of A[0], A[1], A[2] and taking one of A[3], A[4].
N可以在最高50如何处理这个问题?
N can be at max 50. How to approach this question ?
由于所有的我
你知道, 1≤艾≤50
,你可以先过滤输入,之后暴力破解变得可行。
Since for all i
you know that 1 ≤ Ai ≤ 50
, you can first filter the input, after which bruteforcing becomes feasible.
您可以随时选择所有素数的子集,因为每个黄金至少是一样好素(任意倍数对于给定的素数 P
,如果一个整数 X
是互质与一些 K * X
,那么它也互质与 P
)。之后,你可以删除选定的素数的倍数,因为他们不能在结果中。
You can always select all primes for your subset, because each prime is at least as good as any multiple of that prime (for a given prime p
, if an integer x
is coprime with some k * x
, then it is also coprime with p
). After that you can remove all multiples of the selected primes, because they cannot be in the result.
有关更多的滤波,考虑以下几点:每个整数都可以被唯一写成素数的乘积,例如:
For even more filtering, consider the following: every integer can be uniquely written as a product of primes, for instance:
2 = 21
6 = 2131
40 = 2351
对于整数 X
,让我们写 X 0
与相应的整所有的质因子具有功率1。例如,如果 X = 40(2 3 5 1 )
,然后 X 0 = 10(2 1 5 1 )
。我们不需要考虑质数与功耗> 1
,因为对于每一个整数是
认为,如果 X
和是
是互质的,那么是 X 0
和是
。既然你只关心子集的大小,可以相互替换 X
按 X 0
。
For an integer x
, let's write x0
for the corresponding integer with all prime factors having power 1. For example, if x = 40 (2351)
, then x0 = 10 (2151)
. We do not need to consider primes with power >1
, because for every integer y
holds that if x
and y
are coprime, then so are x0
and y
. Since you are only interested in the size of the subset, you can replace each x
by x0
.
有低于50,只有14号是没有素数,有电无素因子> 1
There are only 14 numbers below 50 that are no prime and have no prime factor with power >1
.
6, 10, 14, 15, 21, 22, 26, 30, 33, 34, 35, 38, 39, 42
数量减少 X 0
此组的成员。既然有这么几个,你可以简单地暴力破解,以便找到最大的子集。
The reduced numbers x0
are members of this set. Since there are so few, you can simply bruteforce in order to find the biggest subset.