LEDIV - Editorial

PROBLEM LINK

Practice
Contest

DIFFICULTY

SIMPLE

PREREQUISITES

Simple Math

PROBLEM

You are given a list of numbers. You have to find the smalelst number which divides all these numbers.

QUICK EXPLANATION

To the initiated, this question should be a breeze.

  • Find the GCD of the list of numbers.
  • Find the smallest prime factor of the GCD.

EXPLANATION

The GCD of two numbers can be found using the Euclid’s Algorithm.

gcd(a,b)
    return (b == 0) ?
        a : gcd(b, (a mod b))

The GCD of a list of numbers A[1 … N] can be found as

let G = 0

for i = 1 to N
    G = gcd( A[i], G )

The above is intuitive and easy to prove by induction.

Now, the next step is to find the smallest prime factor of the GCD. Calculating this can be done in O(sqrt(N)) time easily.

for i = 2 to floor(sqrt(G))
    if G is divisible by i
        return i
return G  // Since G is prime!

This calculation is probably the most time consuming step in the solution. Although, iterating till sqrt(G) will fit within the time limit, you can make one optimization to make it faster. That optimization is pre-calculation! You can pre-calculate the smallest primes in the factorization of any number by sieving.

Consider the snippet below

smallestPrime[ 2 ... N ] // We will store our answers here
for i = 2 to N
    smallestPrime[i] = i
for i = 2 to N
    if smallestPrime[i] = i
        for j = 2*i to N, step-size i
            smallestPrime[j] = min( smallestPrime[j], i )

Notice how we modify the step in which in the usual Sieve of Eratosthenes, we set the multiples of i as non-prime. In this step now, we are simply updating the smallestPrime array at index j. This is a very clever trick to master while solving problems. When you deal with a problem where you need to perform an operation based on all prime factors of a number (like in this case, we wanted to find the smallest of them), a small code snippet like above is usually needed.

SETTERS SOLUTION

Can be found here.

TESTERS SOLUTION

Can be found here.

9 Likes

@admin will you please forward a case where submission 1563837 fails . ?

When your ‘r’ is divisible by 3 you did not find this. Say r=63.

1 Like

if we check the array elements by dividing with the prime numbers upto the square root of maximum element of the array.

following this i got WA, can you please give flaw in this approach.

my submission id 1565051

That was a huge miss … sorry . .
but sadly that does not fix the error
submission 1565280

http://www.codechef.com/viewsolution/1565258

@admin where is my code failing?

Consider T=1 N=1 A[1]=24371

2 Likes

You logic is completely incorrect. Try this test T=1 N=2 A[1] = 2 * P A[2] = 3 * P where P is large prime say A[1] = 20122, A[2] = 30183.

1 Like

Try the simplest possible test:
1
1
1
:wink:

2 Likes

well … lesson learned …paid for incoherence. .
@anton thank a lot , very much appreciated :slight_smile:

An alternative solution, maybe one that is slightly easier to understand, would be to find all the divisors of the first number, then try each of these divisors on all others numbers and check if they are divisible by it also.

@anton_lunyov:Thanks,i got it :slight_smile:

http://www.codechef.com/viewsolution/1565594

@admin : Can u tell for which cases it is generating wrong anwers ?

#include<stdio.h>
#include<math.h>
long p[1000],y[100005]={0},x[100005];
void sieve()
{
long i,j;
for(i=3;i<=316;i+=2)
if(y[i]==0)
for(j=i*i;j<=100000;j+=i+i)
y[j]=1;
p[0]=2;
j=0;
for(i=3;i<=100000;i+=2)
if(y[i]==0)
p[++j]=i;
}
int main()
{
long t,n,i,j;
sieve();
scanf("%ld",&t);
while(t–)
{
scanf("%ld",&n);
long min=10000000,f=1;
for(i=0;i<n;++i)
{
scanf("%ld",&x[i]);
if(min>x[i])
min=x[i];
}
for(i=0;p[i]<=min;++i)
{
for(j=0;j<n;++j)
if(x[j]%p[i])
break;
if(j==n)
{
printf("%ld\n",p[i]);
f=0;
break;
}
}
if(f)
printf("-1\n");
}
return 0;

}

i know this approach is not good but i want to know the mistake i made.please reply.thanks in advance.

Try this test
1
1
12346

Replace array p[1000] by p[10000]. There are 9592 primes up to 100000.
However this leads to TLE :slight_smile:
http://www.codechef.com/viewsolution/1565776

What is even more fun that your previous solution passes first two tests and get WA on the third test. But the new “correct” version get TLE on the second test which have the following structure: T=100000 N=1 A[1]>90000 is prime. So as you see you perform about 9000 operations in average for each number. This is about 900 millions operations in all which of course do not fit in TL.

I can only suggest you to follow the editorial.

1 Like

Due to the lack of space I continue here.

You will be probably interested how you first solution can pass more tests than the corrected version. This is probably because array x[] follows p[] in the memory. So when you iterate over array p[] with condition p[i]<=min after the end of this array you jump to x[] which contain the element x[0] which is prime and it is the answer. So you break here.

1 Like

i am getting same answer as of tester solution .
what is the error?

No, you are NOT.

tester’s solution returns 24371

your solution returns 12186

1 Like

ok…got it…thanks

//