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

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

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

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

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 \lt 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