Tboros_kylie's blog

algorithm for co-prime problem
By Tboros_kylie, history, 6 months ago, In English

Hi guys! I'm trying to find an algorithm or idea for solving this problem:

For array a[] has n element ( 2 <= n <= 10^5 , 1 <= a[i] <= 1e5 ) , find one co-prime number in this array ( if it doesn't have any,print -1) , simply: Find (i;j) ( 1<= i < j <= n) so that gcd(a[i],a[j]) = 1 -> print a[i] and a[j].

Of course, the obvious solution would be to use Euclid's algorithm for each pair (ai, aj), but its pesimistic complexity is n(n+1)/2 times the complexity of Euclid's algorithm.

Is there a way to do that in O(n) or O(n*log(n)) or better ?

I find this post: https://stackoverflow.com/questions/26948793/finding-whether-there-are-two-coprime-numbers-in-an-array?fbclid=IwAR27s_3krUKgvYiZJg6MR2TnPreGrCNgkyIjnwlKVln_kIg20LZwykO2Glc

But it doesn't give what i need , so i hope anyone can help me.

Thank you!

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it
My solution
→ Reply
  • »
    »
    6 months ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    If I understand your algo right, there's a counterexample: [6, 8, 9].

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

      yeah you're right

      I think I got AC with weak tests

      UPD : my problem was $$$1 <= a[i] <= 2*n$$$ instead of $$$1 <= a[i] <= 10^5$$$

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

Call a set mutually coprime if for all $$$i \ne j$$$, $$$\gcd(i, j) = 1$$$.

Claim: The size of a mutually coprime set is bounded by above by $$$9593$$$.

Sketch: Each prime can appear at most once in the set. Since we have $$$9592$$$ primes that are $$$\le 10^5$$$, the max size of a mutually coprime set is bounded by above by $$$9592 + 1$$$ (since we could also have $$$1$$$ appear in the set, in addition to those primes).

So our algorithm could look something like this:

  • Remove all occurrences of $$$1$$$ in our array, since that doesn't affect anything.
  • If we ever have a pair of elements $$$i \ne j$$$ where $$$arr[i] == arr[j]$$$, we're done. So we can assume that our array has distinct elements.
  • If our array size is greater than $$$10^4$$$, Choose $$$10^4$$$ elements at random from our array. It is guaranteed by our previous claim that at least one pair of these $$$10^4$$$ elements are coprime. We can find this naively with ~ $$$10^8$$$ operations.
  • If our array size is less than $$$10^4$$$, do the naive way.
→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    If I understand correctly, your algorithm finds (i,j) such that gcd(a[i], a[j]) =/= 1.

    But we want to find (i,j) such that gcd(a[i], a[j]) = 1 instead.

    Nice solution for solving the misread version though.

    → Reply
»
6 months ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

I have a solution which works in O(64n).

First observe that there are at most 6 primes that divides a[i] since 2*3*5*7*11*13*17 > 1e5.

For each index i, you can count the number of indices j such that gcd(a[i], a[j]) = 1 by using the principle of inclusion and exclusion on the prime divisors of a[i]. Implemented with a frequency array, you can count this in O(2^6) time for each i. (Read editorial for https://codeforces.com/contest/547/problem/C if you still need help working out the details.)

Then, using the above count, you can find any a[i] such that the number of coprime elements to it is nonzero. Finally you can search for the index j for which gcd(a[i], a[j]) = 1 in O(nlogn) naively.

The total complexity is O(2^6n + nlogn) = O(64n).

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

I have an idea, you can use a linear sieve to save the lowest prime factor of each number up to 1e5.
Create a vector of vectors v of size 1e5.
Then for each number in the array decompose it in logn and for each factor f add the number to v[f], if at any point you have another number there then those 2 are coprime. And to avoid duplicates you can add a number at most once to v[f].
In total, this is O(n*log(maxi_a[i])+maxi_a[i]), although you can optimize and only add factors smaller than sqrt(maxi_a[i]) in v and then it would be O(n*log(maxi_a[i])+sqrt(maxi_a[i]))

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

    This has the same issue as Olympia's solution. Your algorithm finds a pair of elements which are not coprime. We want to find a pair of elements which are coprime.

    For example if a = [2, 2], your algorithm finds (i,j) = (0, 1), and so gcd(a[0], a[1]) = 2. Which means elements (i,j) are not coprime.

    → Reply