Vasiljko's blog

By Vasiljko, history, 3 years ago, In English,

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

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

TL: 0.6s
ML: 64MB

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

Preprocess all the primes smaller than 108 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 1 * p 2 * ... * p k. (We, again, disregard multiplicity). Note that the time allows us to go through all subsets of {p 1, p 2, ..., 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.

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

»
3 years ago, # |
Rev. 3   Vote: I like it +6 Vote: I do not like it

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 104.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hvala obojici :)

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 ≤ 108. TL = 0.6s. Problem statements are traditionally long and full of unnecessary details and stories.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you please provide that solution

»
5 months ago, # |
  Vote: I like it +26 Vote: I do not like it

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}) $$$
  • »
    »
    4 months ago, # ^ |
      Vote: I like it -32 Vote: I do not like it

    Can you please explain your logic with some example? I mean how will it manipulates in code.. Thanks in Advance :D

  • »
    »
    4 months ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

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

»
4 months ago, # |
Rev. 2   Vote: I like it -13 Vote: I do not like it
I have this approach, but I dont know is this a good way. Correct me if I am wrong
  • »
    »
    4 months ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

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

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it -13 Vote: I do not like it

      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 ?

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 5   Vote: I like it -13 Vote: I do not like it

      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))

»
4 months ago, # |
Rev. 2   Vote: I like it -18 Vote: I do not like it

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 sizeofmapC2 from the answer.
Edit: the above idea of 2 numbers being co-prime is just an observation. Point it if i'm wrong

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    False: 10, 15

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    What the hell is SPF? Googling doesn't give much after filtering out sunscreen and sender policy framework.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      smallest prime factor. ignore it though i'm very very wrong in my solution ,i didn't realize it.