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
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
6 | adamant | 157 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
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
Name |
---|
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
Actually a(I) and a(j) are factors of k
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 < 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
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.