PROBLEM LINK:
Author: Lalit Kundu
Tester: Shiplu Hawlader
Editorialist: Praveen Dhinwa
DIFFICULTY:
Simple
PREREQUISITES:
ad hoc, simple combinatorics.
PROBLEM:
You are selecting two numbers x and y such that 1 <= x <= N and 1 <= y <= M. How many (x, y) pairs satisfy the condition that x + y is odd.
QUICK EXPLANATION

Use the fact that Number of even numbers from 1 to N are floor(N / 2) and number of odd numbers from 1 to N are ceiling(N / 2).

Answer will be (floor(N / 2) * ceiling(N / 2)) / (N * M).

For representing the fraction in lowest terms, divide both the numerator and denominator by gcd of both.
EXPLANATION
Notice the following simple facts.

Sum of an even and an odd number is odd.
ie
Even + Odd = Odd.
Odd + Even = Odd. 
Number of even numbers from 1 to N are floor(N / 2).
Number of odd numbers from 1 to N are ceiling(N / 2).
Fact number 1 is very easy to prove.
Let us prove fact 2, first part.
Claim Number of even numbers from 1 to N are floor(N / 2).
Proof:
We will prove this fact by using induction over N.
Base Case:
For N = 1, floor(1 / 2) = 0. Hence LHS = 0
As number of even numbers are 0 too from 1 to 1. Hence RHS = 0
So LHS = RHS
Induction Hypothesis:
Let us assume that formula is true up to N such that N is even, then we need to prove the formula for N + 1.
Notice that N + 1 will be odd. Hence number of even numbers won’t increase and will remain equal to floor(N / 2).
As we know if N is even, then floor(N / 2) = floor((N + 1)/ 2). Hence we are done for this case.
Now Let us assume that formula is true up to N such that N is odd, then we need to prove the formula for N + 1.
Notice that N + 1 will be even. Hence number of even numbers increase by 1, hence they will be equal to floor(N / 2) + 1.
As we know if N is odd, then floor(N / 2) + 1 = floor((N + 1)/ 2). Hence we are done for this case too.
Note that instead of proving it formally, you can just see the above observation by observing the pattern for small numbers.
Proof of second part of fact 2 (Number of odd numbers from 1 to N are ceiling(N / 2).) will also go exactly along the same lines.
So finally our answer will be (floor(N / 2) * ceiling(N / 2)) / (N * M). We need to print this fraction in its irreducible form, so we have to divide both
the numerator and denominator by their gcd.
 Computing floor(N / 2) can be done by using simply integer division N / 2.
 Computing ceiling(N / 2) can be done by using simply integer divide (N + 1) / 2.
Complexity
O(log(N * M)), in the computation of gcd.
Things to Take Care
 Beware of the overflow of the product N * M, So use long long for storing product N * M.