temp1967's blog

LCM with value k
By temp1967, history, 7 months ago, In English

Can any one tell how can we find the pairs in an array such that LCM(a[i],a[j]) is equal to k where k<= 10^6 and 1<=i,j<=n where n<=10^5 also a[i] for any 1<=i<=n a[i]<=10^6 and also a[i] and a[j] are factors of k

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it -9 Vote: I do not like it

if K is 12 and you have one of the pairs is 4 then the other number could be 3 , 6 , 12 , and bcz a[i]<=1e6 then you can tell it has something to do with prime factors , sieve would be useful

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by temp1967 (previous revision, new revision, compare).

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by temp1967 (previous revision, new revision, compare).

→ Reply
»
7 months ago, # |
  Vote: I like it +17 Vote: I do not like it

remove all elements that are not divisor of k as they cannot form a valid pair
The number of divisors has $$$O(n^{1/3})$$$ upper bound so you can just bruteforce after removal

→ Reply
»
7 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Factor $$$K$$$ into $$$p_1^{e_1} \cdot p_2^{e_2} \cdot ... \cdot p_a^{e_a}$$$. There can be at most $$$7$$$ prime factors. Factor each $$$a_i$$$ in the same way.

Now let's take some random $$$a_i$$$. Let's say that it is $$$p_1^{f_1} \cdot p_2^{f_2} \cdot ... \cdot p_a^{f_a}$$$. Note that the pair, $$$a_j = p_1^{g_1} \cdot p_2^{g_2} \cdot ... \cdot p_a^{g_a}$$$ must satisfy all the following:

$$$max(f_1, g_1) = e_1$$$

$$$max(f_2, g_2) = e_2$$$

$$$\dots$$$

$$$max(f_a, g_a) = e_a$$$

If $$$a_i$$$ has some $$$f_k = e_k$$$ then that imposes no restriction on $$$g_k$$$. But if $$$f_k < e_k$$$ then $$$g_k$$$ must equal $$$e_k$$$. This way we can get an idea to turn each number into a bitmask. It will have the $$$k$$$-th bit set iff $$$f_k = e_k$$$. Now you want pairs of $$$i$$$ and $$$j$$$ such that their bitwise or equals $$$2^a - 1$$$. This should be enough for you to understand how to solve up next, if you don't then reply to this comment and I will try to explain further

→ Reply
  • »
    »
    7 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    ya if we convert each number into a mask for each bit representing a prime factor that means if the number contains all bits set that means all the number are present in same count with respect to k and for finding the j's we want to do find the mask having subset as this for that we can use sum over subsets concept. Thank you understood.

    → Reply