gcd, binomial number

Problem: UVa 530 Binomial Showdown

这道题我用了cache + online computation, 一小部分数据先算好，不在表里的现算，在表内的直接查表

typedef unsigned long long uLL;
uLL gcd(uLL a, uLL b) {
    if(a % b == 0) 
        return b;
    else
        return gcd(b, a%b);
}

void divbygcd(uLL &a, uLL &b) {
    uLL g = gcd(a,b);
    a /= g;
    b /= g;
}

uLL combination(int n, int k) {
    uLL num = 1, den = 1, tomul, todiv, i;
    if(k > n/2) k = n-k; //use smaller k
    for(i = k; i; --i) {
        tomul = n-k+i;
        todiv = i;
        divbygcd(tomul, todiv);
        divbygcd(num, todiv);
        divbygcd(tomul, den);
        num *= tomul;
        den *= todiv;
    }
    return num / den;
}