Topics

GCD & LCM

Sieve

Prime Factorization

Finding Divisors

Number of Divisors

Sum of Divisors

Euler phi (Euler's Totient Function)

Factorial

Extended Euclid

Euler Theorem and Fermat's Little Theorem

Big Integer in C++ for Contest

Number Theory Level 1

GCD & LCM

• Concepts :

  • GCD
    
    
  • LCM
    
    

• Related Problems :

  • UVA 10407 : Solution

  • UVA 10892 : Solution

  • UVA 11388 : Solution

  • UVA 11417 : Solution

  • UVA 11827 : Solution

  • UVA 12068 : Solution

  • UVA 408 : Solution

  • UVA 412 : Solution

Sieve

• Concepts :

  • General Sieve
    
    
  • Bitwise Sieve
    
    
  • Segmentation Sieve
    
    

• RELATED PROBLEMS :

• General Sieve :

  • UVA 10042 : Solution

  • UVA 10168 : Solution

  • UVA 10235 : Solution

  • UVA 10533 : Solution

  • UVA 10539 : Solution

  • UVA 10789 : Solution

  • UVA 406 : Solution

  • UVA 543 : Solution

  • UVA 686 : Solution

  • UVA 917 (Failed to add link) : Solution

• Bitwise Sieve :

  • UVA 10394 : Solution

  • UVA 10699 : Solution

• Segmentation Sieve :

  • SPOJ PRIME GENERATOR : Solution

  • UVA 10140 : Solution

Prime factorization

• Concepts

  • Prime Factorisation of a Number
    
    
  • Prime Factorization For multiple Queries By least prime method
    
    

• Related Problems

  • Codeforces 1370C : Solution

  • UVA 10392 : Solution

  • UVA 10738 : Solution

  • UVA 11466 : Solution

  • UVA 583 : Solution

Finding Divisors

• Concepts

  • Finding Divisors of a Number N
    
    

• Related Problems :

  • Light OJ 1014 : Solution
    
    
    

Number Theory Level 2

• Number of Divisors

  • Concepts

    • Number of Divisors for Any Number N
      
      
    • Pre Calculating Number of Divisors from 1 to N
      
      

  • Related Problems

    • Light OJ 1109 : Solution

    • Light OJ 1336 : Solution

    • SPOJ COMDIV : Solution

    • UVA 294 : Solution

• Sum of Divisors

  • Concepts

    • Sum of Divisors For a N
      
      
    • Pre Calculating Sum of Divisors from 1 to N
      
      
    • Given a Number N find the sum of actual divisors from 1 to N in O(Sqrt(N))
      
      

  • Related Problems :

    • LightOJ 1054 : Solution

    • LightOJ 1098 : Solution

    • SPOJ DIVSUM : Solution

    • SPOJ DIVSUM2 : Solution

• Euler Phi

  • Concepts :

    • Euler Phi for a Number N
      
      
    • Euler Phi From 1 to n in O(nloglogn)
      
      
    • How many Numbers from 1 to N has GCD(i,N) = g
      
      
    • Calculate the SUM = LCM(1,N) + LCM(2,N) + LCM(3,N)+... + LCM(N,N)
      
      

  • Related Problems :

    • Codeforces 1295D : Solution

    • LightOJ 1007 : Solution

    • SPOJ ETF : Solution

    • SPOJ LCMSUM : Solution

    • UVA 10179 : Solution

    • UVA 10820 : Solution

    • UVA 10990 : Solution

    • UVA 11064 : Solution

    • UVA 11327 : Solution

    • UVA 12425 : Solution

    • UVA 13132 : Solution

• Factorial

  • Concepts
    
    

    • Digits of a factorial
      
      
    • Digits of a factorial in Different Base
      
      
    • Pre Calculating Digits of N! in different bases
      
      
    • Factorial Factorisation
      
      
    • Pre Calculating No of Factors from 1! to N!
      
      
    • Dividing a large factorial number N! by a number M
      
      
    • Number of Trailing Zeroes in N!
      
      
    • For a Given Number N how many Number system will have trailing zeroes
      
      
      

  • Related Problems
    
    

    • LightOJ 1028 : Solution

    • LightOJ 1035 : Solution

    • LightOJ 1045 : Solution

    • LightOJ 1090 : Solution

    • LightOJ 1340 : Solution

    • UVA 10061 : Solution

    • UVA 10780 : Solution

    • UVA 11415 : Solution

    • UVA 160 : Solution

    • UVA 884 : Solution
      
      
      

Number Theory Level 3

• Extended Euclid

  • Concepts
    
    

    • Explanation of Extended Euclid
      
      

  • Related Problems
    
    

    • UVA 10104 : Solution
      
      

• Euler theorem and Fermat's Little theorem

  • Concepts
    
    

    • Explanation of Euler theorem and Fermat's Little theorem
      
      

• Big Integer

  :

  • Concepts
    
    

    • Big Integer Library for Contests