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 ?
But it doesn't give what i need , so i hope anyone can help me.
Thank you!
If I understand your algo right, there's a counterexample: [6, 8, 9].
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$$$
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:
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.
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://mirror.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).
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]))
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.
Oh my bad i read it wrong