Two arrays A and P are given where a have N elements and P have M elements.All the elements of P are prime.There is some change you can make on A .You can pick any element Ai (where 0<= i < N) and increase or decrease it by 1.
Now you need to calculate the minimum number of times you need to increase or decrease the elements of A so that every element of A is divisible by at least one element of array P.
1 <= N,M <= 1000000
1<= Ai<= 1000000
1<= Pi<= 1000000
Please can anyone tell the method to solve the problem optimally.
Use sieve to find all the numbers that are divisible by the elements in P. (Put them in a vector/array) say V.
Sort the vector V.
For each element A[i] find the next nearest element in the vector V ( left and right) using binary search ( lower_bound and upper_bound). Take the nearer of those two to A[i]. The difference will give the min moves for A[i] to become divisible by atleast one of P[i].
Precompute all prime factors of all numbers in range 1 to 10^6 (using sieve of eratosthenes).
Now for start removing prime factors which are not given in array P (use map/set maybe).
Now make an array having value 0 if none of the factor left with that value (after removing). And 1 if at least one factor left.
Now compute prefix sum of that array.
Now use binary search ( upper/lower bound) for computing answer.