SPOJ 15965. PLAY WITH NUMBERS (ENIGMATH)

http://www.spoj.com/problems/ENIGMATH/

Here we need to notice that if A*x - B*y =0 then for A=y and B=x the equation is true. We could have just printed the numbers and finish but the problem asks for the minimum number and for example for this case 2*x-4*y=0 the minimum answer is not 4 and 2 but 2 and 1 :). So here is what we should notice the right formula is x=B/GCD(A,B) and y=A/GCD(A,B)  where GCD means the greatest common divisor of numbers A and B. You can find more info about calculating GCD fast here.

       DOWNLOAD THE FULL SOURCE CODE

Greatest common divisor of 2 numbers.Euclid's algorithm

Here I will explain quickly how to find the greatest common divisor of 2 numbers very fast. First of all Euclid;s algorithm states that GCD(x,y)  equals GCD(x-y,y) which is true for x>y.  But we can improve the performance significantly when replacing the operator "-" with operator % (reminder ) which means GCD(x,y)=GCD(x%y,y) where x>y.

SPOJ 526. Divisors

The problem statement

We need to find the number of divisors of numbers from 1 to 10^6 and then check if that number is a multiplication of 2 distinct primes or not. Fir of all we need to get all the prime numbers, we will use the sieve or Eratosphen. We need to do one more thing in our process of finding the prime numbers. Let us have an array named A[] where A[i] shows the number of divisors of i. Now Initially all the elements of A have a value of 1.(we consider that we had already taken the number 1 as a divisor of every number). Now when we are doing our prime search we need to do the divisor count as well. Here is how prime search worked, when we had a number which was not marked we considered it as prime and then we looped over all the numbers which are divisible to that number and marked them as primes. While doing that we also need to increase the current number of divisors with 1. Here is an example
we are now on number 2 which sis a prime that means that we must loop over the number 4,6,8,10...1000000 and mark them as not primes, also we will increase A[4],A[6],A[8].....,A[1000000] with 1 by saying that all these numbers are divisible on 2.
After calculating the primes and the number of divisors of 1 million numbers we can move on to the second step by checking if the elements in the array A have the form of A[i]=p*q (p and q are distinct primes). First of all we need to keep the prime numbers in some array. Then for every number in the array A[i] we need to do a brute force loop. We need to loop over all the primes numbers starting from the lowest and check for the condition.
Check out the source code for a better understanding.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 11063. AP - Complete The Series (Easy)

problem statement

This problem requires dealing with formulas. We will call the series A,we have A[3] and A[N-2] and S. We don't know N yet. We know the formula for the sum which is ((A[1]+A[N])/2)*N it is the same as we replace A[1] with A[3]-2*D and a[N] with A[N-2]+2D which gives (A[3]-2D+A[n-2]+2D)/2*N whic equals to (A[3]+A[n-2])/2 * N =S where the N is the only unknown element so N=2*S/(A[3]+A[N-2])
After finding N we need to find D. so
A[3]=A[1]+2*D
A[n-2]=A[1]+(n-3)*d;
If we subtract the 2 equations above we will get the following
A[n-2]-A[3]=(n-5)*d where d=(A[n-2]-A[3])/(N-5)

       DOWNLOAD THE FULL SOURCE CODE

prime factorization

Prime factorization is a representation of a number as a multiplication of prime numbers.

If the problem you are solving has many test cases you better use the method 1 otherwise use the method 2.

Method 1 slow but useful when you need to factorize many numbers

Generate all the prime numbers in the needed range using the sieve of Eratosphen (which takes O(NlogN) ).
Now loop over the array of found primes until the number gets smaller than the current prime and check if the number is divisible on the current prime. If yes then divide the number into the found prime until it becomes non-divisible on that prime.
Here is the pseudocode

suppose we have the array of found primes called prime[10000]
and our number is N
for(  i=1 continue until a[i]<N)
{
        if( N is divisible on a[i])
        {
             divide N on a[i] until N becomes non divisible on N and keep track of the number of divisions
         }
}


method 2

Loop over numbers from 1, and our loop will end until our N becomes 1. If we found a number on which is divisible on and divide N on that number until it becomes non-divisible to that number. This method works the  same way as the previous method does. Of course the first number which we will find will be prime and other numbers won't be divisible on already found numbers.
 Use the method 1 if you have a problem which requires to factorize many numbers, if you have one big number you better use the second method.




              

finding all prime numbers in [1;N] for O(nlogn).the sieve of Eratostenes

Suppose we need to find all prime numbers between 1 and N. Usually we check if the number is prime by looking at the numbers from 1 to sqrt(K) (K is the number we want to check for). If we want to find all the prime numbers between 1 and N using this method we will have a time limit problem. It will take N*sqrt(N). There is a better way of finding the number in NlogN time. For this we will need a boolean array A[N]. A[i] will be false if the number i is prime otherwise it will be true.
 Here is the pseudocode of the sieve of Eratosfen.
    for(i=2;i<=N;i++)
    {
         if( a[i] is false)
         {
               mark all the divisors of i as true.
         }
    }
lets look at that on a small example
1 2 3 4 5 6 7 8 9 10
f  f  f  f  f  f  f  f  f   f
 number 1 is not prime but we will keep that as false.
Now our loop will continue until it meets a false value. It is the number 2.
2 is prime so our condition is met. Now we know that every number which is divisible on 2 is not a prime number . We go through the number form 2 to 10 and check if the current number is divisible on 2 we mark it as true ( not prime).
1 2 3 4 5 6 7 8 9 10
f  f  f  t  f  t  f  t  f   t
Next step is checking 3. 3 is false which means that 3 is prime so we do the same action again.
We loop through all the numbers and mark the numbers which are divisible on 3 (except 3 himself)
1 2 3 4 5 6 7 8 9 10
f  f  f  t  f  t  f  t  t   t
Now we are checking 4. 4 is true which means that we know that 4 is not prime.
We move to next step.
5 is false so we have to mark all the number which are divisible on 5
1 2 3 4 5 6 7 8 9 10
f  f  f  t  f  t  f  t  t   t
So, we got that 2,3,5,7 are primes in 5*log10


IF YOU HAVE ANY QUESTIONS LEAVE THEM IN COMMENTS NO QUESTION WILL BE UNANSWERED.

finding the greatest common divisor of 2 numbers in O(logn).Euclid's algorithm

We usually find the greatest common divisor of 2 number in this way. We find the prime factorization of two numbers.
a=p1^a1*p2^a2*....*pn^an
b=q1^b1*q2^b2*...*qn^bn
And we choose common prime factors and multiply them to find the greatest common divisor. There is a better approach to this problem.
   We will call the function of finding the greatest common divisor GCD(a,b).
   Euclid's algorithm suggests that GCD(a,b)=GCD(a%b,b) (When a is greater than b)
   Here is the code for finding GCD(a,b);
    int GCD(int a,int b)   // we consider that a is greater than b from the beginning
    {
          while(b>0)
          {
                a=a%b;
                swap(a,b);/// because we considered that a is always greater than b and it is clear that a%b<b)
          }
          return a;
     }

          

Calculate a^n (a power of n) in O(logn)

   We can always calculate A^N by multiplying A with A N times.

    ans=1;

    for(i=1;i<=n;i++)

    {

            ans=ans*a;

     }

This will take O(n) time. There is another way of calculating A^N in O(logn) time.

We can translate the code above in a different way.

    ans=1;   

    while(n>0)

    {

         ans=ans*a;

         n=n-1;

     }

The code above "means" subtract 1 from n until it reaches 0 and in the same time multiply the answer with a.

As we know from our math classes A^B*A^B=(A^B)^2= A^(2*B).  Using this we can cut our N into half (if it is an even number) and instead of multiplying our answer with a we will simply multiply our answer by itself. 

   ans=1;   

    while(n>0)

    {

         if(n%2==0)

         {

               ans=ans*ans;

               n=n/2;

         {

         else

         {

               ans=ans*a;

               n=n-1;

          }

     }

The code is generally right , but there is one problem. If n is divisible on 2 from the beginning we will get a wrong answer because of the following.

when ans=1  and n%2==0 ( n is divisible by 2) we will cut n into half but the answer won't change becuase 1*1=1

   So we better  begin with ans=a and n=n-1

    ans=a;

    n=n-1;  

    while(n>0)

    {

         if(n%2==0)

         {

               ans=ans*ans;

               n=n/2;

         {

         else

         {

               ans=ans*a;

               n=n-1;

          }

     } 

IF YOU HAVE ANY QUESTION LEAVE THEM IN COMMENTS. NO QUESTION WILL BE UNANSWERED

   

     

Euler function

Euler function

   Euler function is often called a function phi(n) shows the number of integers between 1 and n which are coprime with n. 

E(1)=1;

E(2)=2;

E(3)=3;

...

...

...

The Euler function can be calculated with prim factorization but here are some tips on calculating it faster.

1. If p is prime than E(p) = p-1 because every prime number is coprime with every number except itself.

2. If p is prime and a is an nteger than E(p^a) =p^a_ p^a-1   

3. If a and b are coprimes then E(a*b)=E(a)*E(b)

If  n=p1^a1*p2^a2*p3^a3*....*pn^an = (p1^a1-p1^(a1-1) ) * (p2^a2-p2^(a2-1)) * (pn^an - pn^(an-1)) = n * (1-1/p1) * (1-1/p2) * (1-1/p3) * ....* (1-1/pn)

Here is the function in C++ for calculating euler function

int phi (int n)
{
   int ans=n;
   for (int i=2; i*i<=n; ++i)
   if(n%i==0)
   {
while(n%i==0)
    n=n/i;
     ans=ans-ans/i;
   }
   if(n>1)
ans=ans-ans/n;
 return ans;
}