Some idea regarding this problem

Правка en4, от dca, 2020-08-01 01:11:39

I am given an integer array $$$A$$$ of size $$$N$$$. I want to make a multiset from $$$A$$$ such that, if any two elements of the multiset are multiplied, the product should not be a perfect cube. What is the maximum size of the multiset? I can only think of the bruteforce approach. Can we solve it in some efficient way? For example, if A=[1,2,4]. We can create a multiset M=[1,2]. As multiplication of 1*2 is not a cube. Similarly, M can also be [1,4], but not [1,2,4] as 2*4=8, is a cubic number. $$$N<=1000$$$, $$$1$$$ $$$<=Ai<=$$$ $$$10^6$$$

Теги #number theory, #math

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский dca 2020-08-01 01:11:39 6 Tiny change: 'n integer $A$ of si' -> 'n integer array $A$ of si'
en3 Английский dca 2020-08-01 01:06:37 30 Tiny change: 'c number. ' -> 'c number. $N<=1000$, $1$ $<=Ai<=$ $10^6$'
en2 Английский dca 2020-08-01 01:05:30 182
en1 Английский dca 2020-07-31 06:10:05 339 Initial revision (published)