given two arrays find the number of pairs (a,b) from the given array such that their gcd(a,b) != 1
constraints
1<= N < 2*10^5
1<= Ai <10^5
1<= Bi <10^5
Input
A[]={2,4} , B[]={4,2}
Output
4
Input
A[]={2,5,6} , B[]={4,10}
Output
5
More information is needed.
- Constraints for A_i
- Is it from an ongoing contest?
1 Like
No it is not from any contest, it is a genuine question
please check it i had given Constraints
I thought of an approach. Unfortunately, it fails for some test cases.
My approach (too Vague) was to factor elements from arrays A and B and keep track of the powers of primes in two separate vectors. Apply simple combinatorics formula to it. But it is not the correct approach.
May be, @cubefreak777 can help us.
are all elements distinct or can be repeated?
Since the constraints on the elements is small (pow(10,5)), what if we calculate all primes till sqrt(pow(10,5)) ie 316 and there are only 65 primes till 316. Now iterate on these primes and check the multiples of that prime in array A and same with array B and multiply their counts but make sure you didn’t count the same pair again with some other prime. Eg A = [6] B = [12] both the elements are divisble by 2 so we will add 1*1 in our answer but we will not count those again when considering 3 as prime because these two pairs are same.
Kindly correct me if I’m wrong.
Thanks
yes! this will be accepted.
Since the constraints are reasonably small, you can do the following.
Precompute a list of prime factors for all values from [1,10^6]. We don’t require the degree of prime factors, only the prime values themselves would suffice.
Now we go each A_i and iterate over all subsets of the pre-computed prime list of A_i and maintain a count of the number of times product of each subset occurs in the array.
All that remains now is to apply trivial inclusion-exclusion and get the final answer
R=\sum_{i=2}^{10^6}C_A[i]\times C_B[i] \times S_i\times(-1)^{S_i+1}
C_A[i] → Count of number of subsets which have the product i from A
C_B[i] → Count of number of subsets which have the product i from B
S_i → Number of prime factors of i.
CODE FOR REFERENCE
Asympotics: \mathcal{O}(M\log M)), \ M=\max(A_i)
2 Likes
This won’t pass unless you state how will you prevent overcounting clearly. Also the prime precomputation is slow.
1 Like
Hello everyone,I am new to codechef, why my code is not getting accepted even if it is working well in colab or jupyter notebook. the question was
Write a program, which takes an integer N and if the number is less than 10 then display “Thanks for helping Chef!” otherwise print “-1”.
it very else question of if else just try check if you are doing every thing correctly