Help in AC run first problem?

I am trying to solve this problem but not getting the idea to solve this can you help guys to solve
this problem : Contest Page | CodeChef

If all elements are 1, then answer is -1. Else chose the prime p which divides maximum number of A[i]. Is the idea clear?

2 Likes

first part is clear that if all the elements are 1 then any a[i] = a[i]*a[j] will also be 1 we can’t be able to make the gcd(array) >1
but can you explain the second case: “Else chose the prime p which divides maximum number of A[i]”

Use that prime to make all other numbers multiples of that prime. Since GCD() > 1, it has some prime factor so to minimize number of operations we use the prime factor which divides maximum numbers.

Let’s understand it with an example:
Given array:

2 3 5 2 2

Let count[i] denote the number of Integers (in the array) that are divisible by prime i
So, now we have:
count[2] = 3
count[3] = 1
count[5] = 1
Now, we should choose one from the set {2, 3, 5}, and multiply some elements in the array with that element.

  1. If we choose 2, it is enough to multiply the array elements {3,5} with 2 to make the GCD of array > 1.
  2. If we choose 3, we need to multiply [2,2,2,5] with 3 to make GCD of array > 1.
  3. If we choose 5, we need to multiply [2,2,2,3] with 5 to make GCD of array > 1.

Out of all choices, choosing 2 is an optimal solution. So, our answer is the number of operations we perform, i.e., 2

what about this e.g:
2 3 5 32 9
count[2] = 6
count[3] = 3
count[5] = 1
ans = ?

You understood wrong.
count[2] = 2
count[3] = 2
count[5] = 1
count[i] is count of A[j] such that i divides A[j].
Then answer is 5 - 2 = 3.

ohh thanks now got it

I was clear so far :thinking:. Can you mention the phrase which tells I understood it wrong.
Got it, anyways both mean the same. Here’s another example

arr = [4, 4, 3, 6]

count[2] = 3
count[3] = 2
So, according to me, choose 2. But it isn’t there in the array. What I meant was, choose some multiple of 2 which is present in the array and multiply other elements (which are not divisible by 2) with the chosen element. Both imply same.

could you tell why it guarantee minimum number of operation ?

GCD() > 1, hence there is some prime number which is a common factor of all the numbers. So we try all the prime numbers, from 2 to 1000000. Consider any prime p, find the count of numbers which are not divisible by p. Take minimum over those.

yeah make sense

What is this spf thing that everyone has done in the code? I mean is it faster than the usual sieve thing that we do or is it the same?

USUAL_SIEVE SOLUTION
#include "bits/stdc++.h"
using namespace std ;
const int mxA=1e6+1 ;
vector<int>P[mxA] ; 
void solve(){
	int n,mx=-1;cin >>n ;
	map<int,int>mp ;
	for(int i=0,x;i<n;i++){
		cin >> x  ;
		for(int c:P[x])
			mp[c]++,mx=max(mx,mp[c]) ;
	}
	cout<<(mx==-1?-1:n-mx)<<'\n' ;
}
int main(){		
	for(int i=2;i<mxA;i++){
		if(P[i].size())
			continue  ;
		for(int j=i;j<mxA;j+=i)
			P[j].push_back(i) ;
	}
	int TC ;
	cin>>TC ;
	while(TC--)
		solve() ;
}

It is faster. The code is just storing the prime factors of every number using sieve method only. Its complexity is O(N*log(log(N))). I was doing it in O(N*log(N)).

1 Like

it means we are smallest prime factor for the number then you can easily factorize the numbers by finding the prime numbers

1 Like

can u explain the 5th one i am only able to think about the 20 points solution i am not able to come up with the optimal solution!!

SPF stands for Smallest Prime Factor. We calculate Smallest Prime Factor for Every Integer <= N in " N Log ( Log N ) ) " time. Then it is used for Queries. We can factor any integer less than N in Logarithmic Time.

Oh, my bad. I thought you replied to me. Anyways, what you said is correct. i haven’t looked at the previous reply, thought you replied to me. Hope @vkkr125 is clear with the problem.

What’s your 20 points solution? I was trying to optimize it but realized that the problem required working with different cases.
Anyways, tell me your 20 points, I’ll try to optimize that.