The definitions of GCD and LCM are well-known, (and taught in middle school I think) I will skip the definitions. Also, since , calculating GCD is equivalent to calculating LCM. Now, how do we calculate the GCD of two numbers? A naive solution would be iterating over all positive integers no more than . This will get the GCD in , very very slow. We can calculate the GCD of in using Euclidean Algorithm. This algorithm uses the easy-to-prove fact , where is the remainder when is divided by , or just a%b. We can now use the following code. #include <iostream> using namespace std ; int gcd ( int u, int v ) { return u % v == 0 ? v : gcd ( v,u % v ) ; } int main ( void ) { int x, y ; cin >> x >> y ; cout << gcd ( x,y ) ; } How do we prove that this algorithm is ? Well, let's suppose that we started with . Then...