Codechef June 2014 long challenge GUESS - Guessing Game solution

Codechef June 2014 long challenge GUESS - Guessing Game: http://www.codechef.com/JUNE14/problems/GUESS

Codechef June 2014 long challenge GUESS - Guessing Game editorial: http://discuss.codechef.com/questions/44794/guess-editorial

Codechef June 2014 long challenge GUESS - Guessing Game solution: http://ideone.com/PRCoWZ

#include <iostream>
#include <cstdio>
using namespace std;

long long int gcd(long long int u, long long int v) {
    if(u==v) return u;
    if(u==0) return v;
    if(v==0) return u;
    if(~u & 1) {
        if(v&1) return gcd(u>>1, v);
        else return gcd(u>>1, v>>1)<<1;
    }
    if(~v & 1) return gcd(u, v>>1);
    if(u>v) return gcd((u-v)>>1, v);
    return gcd((v-u)>>1, u);
}

int main() {
    int t;
    long long int n, m, a, g, cnt, tot;
    scanf("%d", &t);
    while(t--) {
        scanf("%lld%lld", &n, &m);
        a=n/2;
        if(a*2!=n) a++;
        cnt=a*(m/2);
        a=m/2;
        if(a*2!=m) a++;
        cnt+=a*(n/2);
        tot=n*m;
        g=gcd(tot, cnt);
        cnt/=g;
        tot/=g;
        printf("%lld/%lld\n", cnt, tot);
    }
    return 0;
}

note: pay attn to probability of odd number till N or M or whatsoever. that is ceil(N/2). and now, we got how many odd numbers we can have from 1 to N. we know that sum of two odd numbers makes even, to get odd from two sums, one must be odd and the other should be even, like:
odd+odd =even,
even+even= even,
odd + even = odd, and this is what we are looking for.
we apply probability of odd in N * probability of even in M, because for case N = 2, M = 3,

as you see on the image above, the probability of odd in sum of N + M is 3 out of total 6 chances. thats is 3/6, and when fraction them it is 1/2.