[EP 3] GCD and Totient function.md

Euclidean GCD and Euler's Totient function

You'll see a fair number of easy mathy problems whose solutions involve finding and using the Greatest Common Divisor (GCD) of some numbers. The Euler totient function is rarer, but it is still good to know.

Reading material:

• Euclid's algorithm
  • CPH Ch 21, pg 200
  • CP Algorithms
• Euler's totient function
  • CPH Ch 21, pg 201
  • CP Algorithms
• Topcoder article - click

Problems

• Codechef FLOW016
• CF 664 A
• Spoj CEQU
• Spoj ETF
• CF 1295 D
• CSES Totient sums
• Spoj NAJPWG

Challenging problems

• CF 583 C
• CF 1350 C
• CF 75 C
• CF 1034 A
• CF 803 C
• CF 1152 C

Tip: Use std::gcd or __gcd() (a builtin function of the GCC compiler).