3.Number_Theory.md

Number Theory

	Resource To practice question on Number Theory

• Link : https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=719

  Number Theory (part-1) tutorial (GCD, Factors, Prime)

• Link : https://youtu.be/qHBhRoDkIm4

• Link to pdf : https://drive.google.com/file/d/1_bMmzKpbaNeoCKHQ1lZi8g_DkiPHtHaf/view

• Gcd Algorithm

int gcd(int a, int b)
{
	return (b == 0) ? a : gcd(b, a % b);
}    

• Factors

vector<int> fact(int N)

 {
	vector<int> factor;
	for(int i=1; i<= sqrt(N); i++)
	{
		if(N % i == 0)
		{
			factor.push_back(i);
			if(i != N/i)
			factor.push_back(N/i);
		}
	}	
	return factor;
 }     

• Prime (Sieve algo)

vector<bool> isprime(1e6+1,true);

vector<ll int> primes;

void sieve()

 {

    ll int i,j;
    isprime[0] = false;
    isprime[1] = false;
    for(i=2; i<=1e6 ;i++)
  {

    if(isprime[i])
    {

      primes.push_back(i);
      for(j=i*i; j<=1e6; j+=i)

      {

        isprime[j]=false;

      }

    }

  }

 } 

Number Theory (part-2) tutorial (1 Qustion on sieve, Prime-Factors, Totient Function )

• Link : https://youtu.be/m6uROtdC-q4

• Link to pdf : https://drive.google.com/file/d/1sT7BFhU_SfeWEtQf81qQ1eNbiK7suSIZ/view?usp=sharing

• Question Link : https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=720&page=show_problem&problem=1081

• How to find Prime-factors

vector<bool> isprime(1e6+1,true);

    vector<ll int> primes;

    void sieve()

 {

    ll int i,j;
    isprime[0] = false;
    isprime[1] = false;

    for(i=2; i<=1e6 ;i++)
  {

    if(isprime[i])
    {

      primes.push_back(i);

      for(j=i*i; j<=1e6; j+=i)
      {
        isprime[j]=false;
      }

    }

  }
}

vector<int> primefactors(ll int N)

 {

    vector<int> factors;
    ll pf_idx = 0, pf=primes[pf_idx];

    while(pf*pf<=N)
    {
        while(N % pf == 0)
        {
            N/=pf;
            factors.push_back(pf);
        }
        pf = primes[++pf_idx];
    }
    
    if(N != 1) factors.push_back(N);
    return factors;

}

Important functions to do

1. Count number of prime factors.
2. Count number of distinct prime factors.
3. Sum of all prime factors.
4. Count number of divisors of N.
5. Sum of all divisors of N.

If N can be represented as N = a^i x b^j x ....... x c^k where a, b, c are prime factors of N then -:

No of divisors = (i+1)x(j+1)x......x(k+1)

Sum of divisors = ((a^i+1) - 1 )/(a-1) x ((b^j+1)-1)/(b-1) x ..... x ((c^k+1)-1)/(c-1)

Totient Function

Formula = Eulerphi(N) = N x ((product of all terms)(1 - 1/Prime factor i )) eg N = 36 = 2^2 x 3^2

Eulerphi(N) = N x (1 - 1/2) x (1 - 1/3) = 12

ll int eulerPhi( ll int N)
{

    ll pf_idx = 0, pf=primes[pf_idx];
    
    ll ans=N;

    while(pf*pf<=N)
    {
        if(N % pf == 0)
        {
            ans -= ans / pf;
        }
        while(N % pf == 0) N /= pf;

        pf = primes[++pf_idx];
    }
    if(N != 1) ans -= ans / N;
    return ans;
}    

• Link to Contest 2 based on Number theory : https://codeforces.com/contestInvitation/57cb7c90836ae129ab29d3bda0c850f8fcaa23d8

• Link to editorial : https://youtu.be/J7N-2a4wv-0

    Number Theory (part-3) tutorial (Factorial and cpp_int data type, Modified sieve, Modulo Arithmetic)
  

• Link : https://youtu.be/RY8JzpnX9PU

• Link to pdf : https://drive.google.com/file/d/11-ZpFL1D5VNtSqSH_K3oT-gNf_rgG9fw/view?usp=sharing

   Factorial
  

vector<long long int> factorial(n, 1);

    long long int fact(int n)

    {
        for(int i=1; i<=n; i++)
        {
            factorial[i] = factorial[i - 1] * i;
        }
        return factorial[n];
    }  

Modified sieve to count number of different prime factors of a number directly

vector< int > divisor(1e7+1, 0) ;

    void sieve()
    {
        long long int j;
        for(int i=2; i<=1e7; i++)
        {
            if(!divisor[i])        // i.e prime number
            {
                for(j= i+i; j<=1e7; j+=i)
                {
                    divisor[j]++;                 // after this algo you can find the number of diff P.F 
                                                     in O(1) just by divisor[n].
                }
            }
        }
                
    }       

 Modulo Arithmatics

1. (a + b) % m = ( a % m + b % m ) % m

2. (a - b) % m = ( a % m - b % m ) % m

3. (a * b) % m = ( a % m * b % m ) % m

4. (a^b) % m = (( a % m )^b ) % m

    Number Theory (part-4) tutorial (Extended Euclid Algo, Diophantine EQ., Inverse Modulo)
   

• Link : https://youtu.be/IQQKrcDkfvE

• Link to pdf : https://drive.google.com/file/d/1r_EqMLX3MfiiI_tuxEQGZJ8z4H3uyXD8/view?usp=sharing

  Extended Euclid

    int x, y, d;

    void extended_euclid(int a, int b)

    {
      if(b == 0) {x = 1, y=0, d = a, return;  }
      extended_euclid( b, a%b); // same as gcd
      int x1 = y;
      int y1 = x - (a / b) * y;
      x = x1;
      y = y1; 
    }    

Inverse Modulo

1. Use Extend euclid to calculate inverse multiplicative modulo of a with modulo m by calling above function as extended_euclid(a, m) and the value of x is our inverse.

2. (a / b) % m = ( a % m * (b^-1) % m ) % m = ( a % m * (inv) ) % m // inv = value of x from above

    // Happy Coding //