Number Theory

Basic Questions
FIbbnacci
Bitmasking
Prime Numbers
Gcd & Lcm
Euler Tutoinent
Binary Exponention
Modulo Inverse
Combinations
Number of Intergral Solutions

1. Basic Questions

Sum of squares of first N natural number
Factorial of a Number
Trailing Zeroes in Factorial
Maximum Power Dividing Factorial

2. Fibbnaci

Normal FIbbnaci
Matrix exponention Fibnacci
Sum of N Fibbnaci is is Fib[n+2]-1

3. Bitmasking

Power Set (IMP.)
Two Missing Numbers Link

4. Prime Numbers

Sieve of Erathoneses
Segemented Seive
Prime Factorization Of Number
Count , Sum , Product Of Divisors

5. GCD & LCM

Gcd Eucledian Algo (gcd(a,b))
LDE (Linear Diophanite Equation ) :- ax + by = c; positive or negative value of x and y exist only and only if c%(gcd(a,b))==0;
Extended Euclid Algo :- It basicaly give the value of x and y also if ax+by=__gcd(a,b)

6. Euler Tointent

phi(n) is count of 1 to n-1 where __gcd(i,n)==1
phi(n) if n is prime n-1
phi(n) if n has only one prime factor like 2^3 then p^k - p^k-1
phi(n) is prime factorization then it has multiplicatiive property (p1^k1 - p1^k1- 1)*(p2^k2-p2^k2-1)

7. Binary Exponention

8. Module Inverse (IMP)

modulo inverse is that no. example modulo of a in a*x mod m=1 then here x is modulo inverse of a ;

Modulo inverse can only be find if a and m are coprime

There are mainly 3 ways to find :-

Extended Euclid Basically ax+by=gcd(a,b) then if if(gcd(a,b) is 1 then x is modulo inverse of a (Most Optimized )

Euler theorem it states that a^phi(m)mod m =1 condition is a and m is coprime then a^(phi(m)-1) is modulo inverse

Fermat Little Theorem states that a ^ m =amodm where m is prime then by using it we can find modulo inverse and then inverse is a ^ m-2 condition is m is prime and a is not multipe of m mainly gcd(a,m)==1

Euler Theorem Basic Question

what is last digit of 7 ^ 1002 ?

what is value of 2^1000 mod 13 ?

what is of 5 ^ 99 mod 13 ?

9. Combination

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int fact[100005];
int mod = int (1e9 + 7);
int powerArray[100005];

void preCompute() {
    fact[0] = 1;
    for (int i = 1; i < 100005; i++){
        fact[i] = i * fact[i - 1] % mod;
        powerArray[i]=power(fact[i], mod - 2, mod);
    }
}

int power(int base, int n, int mod) {
    int ans = 1;
    while (n) {
        if (n % 2) {
            n = n - 1;
            ans = (ans * base) % mod;
        }
        else {
            n = n / 2;
            base = (base * base) % mod;
        }
    }
    return ans;

}

void nCr(int n, int r) {
    //return fact[n]/fact[n-r]*fact[r];   SimpleWay
    //return (fact[n] * power(fact[r], mod - 2, mod) * power(fact[n - r], mod - 2, mod)) % mod;   // Fermat Little Theorem
    return fact[n]*powerArray[r]*powerArray[n-r] %mod ;  // Premoute powerArray
}

int main() {
    int n, r;
    cin >> n >> r;
    cout << nCr(n, r);


}

11 Number of Integral Solution

youtube.com/watch?v=6y20cowA3s8
geeksforgeeks.org/number-of-integral-soluti..
Number of non-negative integral solutions of equation x1 + x2 +…+ xn = k is equal to the number of ways in which k identical balls can be distributed into N unique boxes. n+k-1 C k-1

Number of positive integral solutions of equation x1 + x2 + … + xn = k is equal to the number of ways in which k identical balls can be distributed into N unique boxes such that each box must contain at-least 1 ball.

12. Catalan Numbers

2nCn/n+1
sigma of 1 to n C(n-i)*C(i-1)
in second line C is Catalan number

13. Chicken McNugget Theorem

The Chicken McNugget Theorem (or Postage Stamp Problem or Frobenius Coin Problem) states that for any two relatively prime positive integers m,n, the greatest integer that cannot be written in the form am + bn for nonnegative integers a, b is mn-m-n.
A consequence of the theorem is that there are exactly {(m - 1)(n - 1)}/{2} positive integers which cannot be expressed in the form am + bn. Link

karan Wadhwa's Blog