UVA 10689 - Yet another Number Sequence

Problem link

Keyword: Fibonacci number, finding cycle

Algorithm:

For this kind of problems, we usually have to find some cycle.
If you don't know about pisano period, you may simulate the sequence and find out the length of the cycle.
If you do, then just apply the period to this problem and you're home.
The pisano period of the last few digits: one digit→60, two digits→300, three digits→1500, four digits→15000.

Code:

#include<cstdio>

int main()
{
    int t, a1, a2, seq, digit, pisano[] = { 0, 60, 300, 1500, 15000 }, pow10[] = { 1, 10, 100, 1000, 10000 };
    scanf( "%d", &t );

    while( t-- )
    {
        scanf( "%d %d %d %d", &a1, &a2, &seq, &digit );
        seq %= pisano[ digit ];
        a1 %= pow10[ digit ];
        a2 %= pow10[ digit ];
        int *cal = new int[ pisano[ digit ] ];
        cal[ 0 ] = a1, cal[ 1 ] = a2;
        for( int i = 2; i < pisano[ digit ] && i <= seq; ++i )
            cal[ i ] = ( cal[ i-1 ] + cal[ i-2 ] ) % pow10[ digit ];
        printf( "%d\n", cal[ seq ] );
    }

    return 0;
}