UVA 264 - Count on Cantor

Problem link

Keyword: math

Algorithm:

Since it would be too slow to count from the first term to the last term, we must find some formula to calculate the answer in O(1).
The basic idea is that the number of numbers in each slope in increasing at a constant speed 1.(The first slope have 1, the second have 2, and so on.)
Then you can find how many numbers have been written when N slopes are filled, and finally, calculate the difference between the input and the number of numbers filled and find out the specific term.

Code:

#include<cstdio>
#include<cmath>

int main()
{
    int n;
    while( scanf( "%d", &n ) != EOF )
    {
        int sum = ceil( ( sqrt( 1 + 8*n ) - 1 ) / 2 ) + 1, full = sum * ( sum - 1 ) / 2;
        if( sum % 2 )
            printf( "TERM %d IS %d/%d\n", n, n - ( sum - 1 ) * ( sum - 2 ) / 2, full - n + 1 );
        else
            printf( "TERM %d IS %d/%d\n", n, full - n + 1, n - ( sum - 1 ) * ( sum - 2 ) / 2 );
    }

    return 0;
}