You can make a system of linear equations with k+2 variables and equations, which would look like:
A_0 * 1^0 + A_1 * 1^1 + ... + A_(k+2) * 1^(k+2) = 1^k
A_0 * 2^0 + A_1 * 2^1 + ... + A_(k+2) * 2^(k+2) = 2^k
...
A_0 * (k+2)^0 + A_1 * (k+2)^1 + ... + A_(k+2) * (k+2)^(k+2) = (k+2)^k

So, you only need to find A_i coefficients using Gaussion elimination.

Just reduce as much as possoble before actual operation:

tf operator + (const tf& f1, const tf& f2)
{
    int64 d  = gcd(f1.b, f2.b);
    int64 m1 = f2.b/d;
    int64 m2 = f1.b/d;
    return tf(f1.a*m1 + f2.a*m2, f1.b*m1);
}

tf operator - (const tf& f1, const tf& f2)
{
    int64 d  = gcd(f1.b, f2.b);
    int64 m1 = f2.b/d;
    int64 m2 = f1.b/d;
    return tf(f1.a*m1 - f2.a*m2, f1.b*m1);
}

tf operator * (const tf& f1, const tf& f2)
{
    int64 d1 = gcd(f1.a, f2.b);
    int64 d2 = gcd(f2.a, f1.b);
    return tf((f1.a/d1)*(f2.a/d2), (f1.b/d2)*(f2.b/d1));
}

tf operator / (const tf& f1, const tf& f2)
{
    assert(f2.a);
    return f1*tf(f2.b, f2.a);
}

fractions are further reduced inside 'tf(int64, int64)' constructor.

Edited by author 12.08.2008 05:28

I found formula using my math.(it's recursive, but it was rather easy to get AC using __int64)

Yes.

This problem can be solved using __int64 and some good idea.

Good luck!