Number of coprimes - Codeforces

Блог пользователя Vasiljko

Number of coprimes

Автор Vasiljko, история, 6 лет назад, По-английски

Given array of N elements. Find number of coprime pairs.

1 <= N <= 30000
1 <= A[i] <= 10^8

TL: 0.6s
ML: 64MB

Vasiljko
6 лет назад
31

Комментарии (27)

Показать архивные | Написать комментарий?

Brankonymous

6 лет назад, # |

Hmmm, I don't really know. But, I'll let you know as soon as I come up with a solution! (If I come up with one) :D

→ Ответить

The_Wolfpack

6 лет назад, # |

← Rev. 2 →

Preprocess all the primes smaller than 10⁸ by Eratosthenes Sieve.

Now, for all the numbers a_i, make a vector of it's prime divisors (not counting the multiplicity). We will actually find the numbers of non-coprime pairs of numbers and subtract it from n * (n - 1) / 2

Suppose that, for some i, we have a_i = p₁ * p₂ * ... * p_k. (We, again, disregard multiplicity). Note that the time allows us to go through all subsets of {p₁, p₂, ..., p_k} for all i. Build two maps, cnt[] and sgn[]. cnt[X] tells us how many times subset with product equal to X appears in all elements of array a[], while sgn[X] tells us how many elements the subset has.

And for the finale just use the Inclusion — Exclusion Principle.

→ Ответить

e-llusion

4 года назад, # ^ |

← Rev. 2 →

Can you please explain the time complexity part? I couldn't understand how the time is sufficient here. Since the primes vector size is ~1200(number of primes in [1,10000]), won't it take time to iterate through all these primes, for every element (n=30000, so 30000*1200 in the worst case), to get its vector of prime divisors? I am not aware of any other optimized approach here to get the vector. Any further explanation regarding what I am missing would be extremely helpful.

→ Ответить

PerPendIcuL4R

3 года назад, # ^ |

Since a[i] <= 10^8 and the smallest prime number is 2.Consider a[i] has some x number of prime factors(including multiplicity) then a[i] >= 2^x. Using a[i] <= 10^8, we can get maximum value of x can be around 25-30 and hence it satisfies the given time constraints.

→ Ответить

e-llusion

3 года назад, # ^ |

Got It. Thanks!

→ Ответить

dgupta0812

3 года назад, # ^ |

Can anyone show the implementation part ?

I am unable to put the Inclusion Exclusion principle with the rest of solution.

→ Ответить

mychecksdead

3 года назад, # ^ |

← Rev. 2 →

Maybe there is another ways, mine is here: (idk is it late to answer)

int f(int n, vector<int> &arr){
    for(int b = 0; b < (1<<n); b++){
        int x = 0;
        for(int i = 0; i < n; i++) if(b&(1<<i)){
            //process something
            x++;
        }
        if(x == 0) continue; //optional
        if(x % 2){
            //included or vice versa
        }
        else{
            //excluded or vice versa
        }
    }
    return //something;
}

Time complexity: O(n*2^n)

→ Ответить

dgupta0812

3 года назад, # ^ |

No, it's not late. Tysm.

→ Ответить

ivan100sic

6 лет назад, # |

← Rev. 3 →

I'm the author of this task :) It appeared on the national programming competition in Serbia this year.

Problem 6 (In Serbian)

The intended solution for 100 points is what The_Wolfpack has written, with a small correction — you only need to process primes up to 10⁴.

→ Ответить

Vasiljko

6 лет назад, # ^ |

Hvala obojici :)

→ Ответить

meet2mky

6 лет назад, # ^ |

Can I get the aforementioned problem in English? I really liked that concept. Thank You very much.

→ Ответить

ivan100sic

6 лет назад, # ^ |

It's identical to the problem posted in the blog: Find the number of pairs i, j (1 ≤ i < j ≤ n) such that gcd(a_i, a_j) = 1. Constraints are: 1 ≤ N ≤ 30000, 1 ≤ a_i ≤ 10⁸. TL = 0.6s. Problem statements are traditionally long and full of unnecessary details and stories.

→ Ответить

aknov711

3 года назад, # ^ |

Can you explain in brief how can we apply inclusion-exclusion after calculating above mentioned things by The_Wolfpack?

→ Ответить

vipbaswan

3 года назад, # ^ |

← Rev. 2 →

If we have stored X = p1*p2, then we would also have stored X=p1 and X=p2 in our maps (because we are traversing over all subsets of distinct primes for each element of the array).

Now, all those pairs of elements which have either p1 or p2 or both p1 and p2 common in their prime factorisation, they can't be co-primes. So, now we can use inclusion-exclusion to find all such pairs.

int allNonCoprimes = 0;
for (auto itr : sgn)
{
   int mul = itr.first, x = itr.second, y = cnt[itr.first];

   //If 4 elements of the array share this product, then 4*3 are 
   //the number of pairs which can't be co-primes (contains 
   //duplicates, 1-2 & 2-1 are counted as distinct)
   int toRemove = y * (y - 1);
   if (x % 2 == 0)
       allNonCoprimes -= toRemove;
   else
       allNonCoprimes += toRemove;
}

→ Ответить

just_try_again

3 года назад, # ^ |

Thank a lot for the info! I was able to solve this codechef problem from your idea. It's not the same but asks us to find the number of triplets.

But there is one mistake in your code. We subtract toRemove if x is odd and add when it's even.

→ Ответить

vipbaswan

3 года назад, # ^ |

Umm, why do we have to subtract toRemove if x is odd? The code just implements the Incl-Excl directly.

Btw, this cses problem also uses this same idea

→ Ответить

Into_Your_Arms

3 года назад, # ^ |

can you tell that 'small correction' so that we only need to process upto $$$10^4$$$. I mean let's say I have number whose prime divisor are >$$$10^4$$$ then how we can check it?

→ Ответить

parveen1981

3 года назад, # ^ |

if there are any prime divisors which are greater than $$$10^4$$$ then the quotient will be obviously less than $$$10^4$$$. And the quotient will have prime factors which are already calculated. So you just divide the number again and again by those prime factors. If you end up with a number greater than 1 then that is also a prime factor.

→ Ответить

Fly_37

4 года назад, # |

+26

I think that there exist a simpler solution, which allow us to calculate this value straightforwardly.

We want to maintain array $$$DP[x]$$$ — number of pairs $$$(a, b)$$$, that $$$GCD(a, b) = x$$$.

Let's iterate over all possible results of $$$GCD$$$ starting from the greatest element in array (lets call it $$$M$$$).

To count $$$DP[x]$$$ we only have to consider elements of array that are multiple of $$$x$$$. If $$$f(x)$$$ is the number of all pairs we can obtain from the set of $$$x$$$ elements, and $$$q(x)$$$ is number of elements that are multiple of $$$x$$$, then

$$$DP[x] = f(q(x)) -\sum_{k = 2}^{floor(\frac{M}{x})} DP[k \cdot x]$$$

The result is of course

$$$DP[1]$$$

Overall complexity:

$$$ O(M\log{M}) $$$

→ Ответить

ivan100sic

4 года назад, # ^ |

-7

It's simpler but unfortunately it won't work here because $$$M = 10^8$$$.

→ Ответить

SPyofgame

4 года назад, # |

← Rev. 2 →

-13

I have this approach, but I dont know is this a good way. Correct me if I am wrong

→ Ответить

ivan100sic

4 года назад, # ^ |

-9

I think you should read the problem again carefully, particularly this comment

→ Ответить

SPyofgame

4 года назад, # ^ |

-13

I think the problem asking about find number of pair(i, j) where 1 ≤ i, j ≤ n and gcd(i, j) = 1.

So I calculate ϕ(j) for every 1 ≤ j ≤ n. Then I will know the number i in range [1..j] that gcd(i, j) = 1

Then I calculate the sum of all ϕ(j) in range [1..n].

Is my approach correct problemsetter ?

→ Ответить

SPyofgame

4 года назад, # ^ |

← Rev. 5 →

-13

Ah, number of pair(ai, aj). Sorry for my reading the problem carelessly

So how about this new approach

For each pair (i, j) that 1 ≤ i ≤ j ≤ n

I increase the result whenever gcd(ai, aj) = 1

Time Complexity: O(n ^ 2 log (n ^ 2))

→ Ответить

omega07

4 года назад, # |

← Rev. 2 →

-18

2 numbers are co-prime if their SPFs are different.
Preprocess all the SPFs and then store the SPFs of the numbers in the array in map.
Now you will have the numbers whose SPFs is the same.
Let ans = n*(n+1)/2 (n = size of the array), now you could iterate through the map and subtract the ^sizeofmapC₂ from the answer.
Edit: the above idea of 2 numbers being co-prime is just an observation. Point it if i'm wrong

→ Ответить