Skip to content

Number_Theory.md

Latest commit

 

History

History
567 lines (337 loc) · 11.2 KB

Number_Theory.md

File metadata and controls

567 lines (337 loc) · 11.2 KB

Number Theory

Binary Exponentiation [1][2]

      - Binary Exponentiation[1]
      - modular multiplication[2]

Problems

LASTDIG - SPOJ 
https://www.spoj.com/problems/LASTDIG/
Solutions
Solution-1 
    #include<iostream>
    using namespace std;


    #define          ll     long long int
    void FLASH() {ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}


    ll bigmod ( ll a, ll p, ll m )
    {
        ll res = 1;
        ll x = a%m;
        if(x==0)return 0;

        while ( p )
        {
            if ( p & 1 )
            {
                res = ( res * x ) % m;
            }
            x = ( x * x ) % m;
            p = p >> 1;
        }

        return res;
    }

    int main()
    {
         FLASH();
         ll t;
         cin>>t;
         while(t--)
         {
             ll a,b;
             cin>>a>>b;
             cout<<bigmod(a,b,10)<<endl;
         }



        return 0;
    }
LOCKER - SPOJ 
https://www.spoj.com/problems/LOCKER/
Solution 
https://palak001.medium.com/spoj-locker-magic-of-the-locker-a758bccf432f
ZSUM - SPOJ 
https://www.spoj.com/problems/ZSUM/
Solutions
Solution-1 
    
    #include <iomanip>
    #include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <string>
    #include <cmath>
    #include <vector>
    #include <set>
    #include <map>
    #include <unordered_set>
    #include <unordered_map>
    #include <stack>
    #include <queue>
    #include <deque>
    #include <iterator>
    #include <bitset>
    #include <assert.h>
    #include <new>
    #include <sstream>
    #include <time.h>


    using namespace std;
    typedef long long ll;
    #define     re                return
    #define     IOS               ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);




    ll bigmod(ll a,ll p,ll m)
    {
        ll x=a%m,res=1;
        if(x==0)re 0;
        while(p){
            if(p&1)res = (res*x)%m;
            x = (x*x)%m;
            p>>=1;
        }
        re res;
    }


    int main()
    {
        IOS;
        ll tst=1;
        //cin>>tst;
        for(ll tt=1;  ;tt++)
        {
            //code
            ll n,k;
            cin>>n>>k;
            if(!n && !k)break;
            ll val=(2*bigmod(n-1,k,MOD))%MOD + bigmod(n,k,MOD) + (2*bigmod(n-1,n-1,MOD))%MOD + bigmod(n,n,MOD);
            cout<<val%MOD<<endl;

        }


        return 0;
    }

Modular Inverse [1][2][3][4]

      - Modular Multiplicative Inverse - forthright48[1]
      - Modular inverse made easy[2]
      - How To Find The Inverse of a Number[3]
      - Modular Multiplicative Inverse - Cp Algorithm[4]

Problems

LOCKER - SPOJ 
https://www.spoj.com/problems/LOCKER/
Solution 
https://palak001.medium.com/spoj-locker-magic-of-the-locker-a758bccf432f

Sieve of Eratosthenes [1][2][3]

      - Sieve of Eratosthenes - forthright48[1]
      - Sieve of Eratosthenes - Cp Algorithm[2]
      - Segmented Sieve of Eratosthenes -  forthright48[3]

Problems

TDPRIMES - SPOJ 
https://www.spoj.com/problems/TDPRIMES/
Solution 
https://ideone.com/k3Ykm0

Euclidean Algorithm [1][2]

      - Euclidean Algorithm(Proof) - Youtube[1]
      - Euclidian Algorithm - FreeCodeCamp[2]

Problems

11827 - Maximum GCD 
https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=2927
Solution 
Solve it!!

Extend Euclidean Algorithm [1][2][3][4][5][6][7]

      - The Extended Euclidean algorithm - Youtube[1]
      - Extended Euclidean Algorithm and Inverse Modulo - FreeCodeCamp[2]
      - এক্সটেন্ডেড ইউক্লিডীয়ান অ্যালগোরিদম - Return 0[3]
      - Extended Euclidean Algorithm - forthright48[4]
      - Linear Diophantine Equation  - forthright48[5]
      - Extended Euclidean Algorithm - Cp Algorithm[6]
      - Linear Diophantine Equation - Cp Algorithm[7]

Problems

Extended Euclidean Algorithm applications 
https://codeforces.com/blog/entry/10575?locale=en
Solution 
Solve them!!

Chicken McNugget Theorem [1][2][3]

      - Frobenius Coin Problem (Chicken McNugget Theorem) - Youtube[1]
      - Number System Concept 4 ( Chicken Mcnugget Theorem) - Youtube[2]
      - Chicken McNugget Theorem - Medium[3]

Problems

Get AC in one go - CodeChef 
https://www.codechef.com/problems/COPR16G
Solution 
https://www.codechef.com/viewsolution/63102204

Binomial Coefficients [1][2]

      - Binomial Coefficient using C++ - Youtube[1]
      - Binomial Coefficients - Cp Algorithm[2]

Problems

Get AC in one go - CodeChef 
https://www.codechef.com/problems/COPR16G
Solution 
https://www.codechef.com/viewsolution/63102204

Sieve of Eratosthenes [1][2][3]

      - Sieve of Eratosthenes, Generating Primes - forthright48[1]
      - Binomial Coefficients - Cp Algorithm[2]
      - Segmented Sieve of Eratosthenes - forthright48[3]

Problems

Get AC in one go - CodeChef 
https://www.codechef.com/problems/COPR16G
Solution 
https://www.codechef.com/viewsolution/63102204


Inclusion Exclution [1][2][3]

      - Sieve of Eratosthenes, Generating Primes - forthright48[1]
      - Binomial Coefficients - Cp Algorithm[2]
      - Segmented Sieve of Eratosthenes - forthright48[3]

Problems

Extreme GCD - LightOj 
[https://www.codechef.com/problems/COPR16G](https://lightoj.com/problem/extreme-gcd)
Solution 
https://github.com/Anikcb/LightOj_Practice/blob/main/Codes/Extreme%20GCD.cpp