Optymalizacja algorytmu silni dla dużych liczb

Witam,
mam problem z algorytmem silnia, testowałem wersje iteracyjną jak i wersję rekurencyjną, ale obie przekraczają limit, moje pytanie brzmi, jak jest zoptymalizować aby nie wyrzucały błędu "przekroczono limit wykonania".
Program ma za zadanie, wyświetlić liczbę dziesiątek i jednostek w silni, która zostaje obliczona.
http://pl.spoj.com/problems/FCTRL3/

z gory dzieki za pomoc :)

#include <iostream>

// zadanie spoj -> dwie cyfry silni
// kod zadania: FCTRL3

using namespace std;

long long silnia_iter(long long n) {
    long long wynik = 1;
    for(unsigned long i = n; i > 0; --i) {
        wynik *= i;        
    }
    return wynik;    
}

long long silnia_rek(long long n) {
    if(n == 0) return 1;
    else return n * silnia_rek(n - 1);
}

int dziesiatki(long long n) {
    return (n / 10) % 10;    
}

int jednostki(long long n) {
    return n % 10;
}

int main() { 
    int t;
    long long n;
    long long nSilnia;
    cin >> t;

    if((t >= 1) && (t <= 30)) {
        for(int i = 0; i < t; ++i) {
            cin >> n;
            if(n >= 0 && n <= 1000000000) { // lol
                nSilnia = silnia_rek(n); // wynik silni dla n
                cout << dziesiatki(nSilnia) << " " << jednostki(nSilnia) << endl;
            }
        }
    }

    return 0;   
}
 

Nie licz silni. Wypisz sobie 10 pierwszych wartości silni (ewentualnie więcej lub mniej) i patrz na nie tak długo aż wpadniesz na lepsze rozwiązanie tego zadania. :)

Hint:
Dla X>=5, X!%10==0
Dla X>=10, X!%100==0

Ok widze, jak to można ominąć na SPOJ :)
Tylko pytanie, czy bez normalnego algorytmu silni to nie przejdzie na SPOJ'u ? Nawet po optymalizacji?
Na SPOJ'u testuje liczby, aż wielkości 1000000000 i dlatego może przekraczać limit?

Na SPOJu liczy sie myslenie, jak jestes w stanie wyliczyc cala ta silnie w podanym czasie to tak zrob. Jednak ja nie znam takiego algorytmu.

Zadania algorytmiczne polegają główne na myśleniu a nie klepaniu kodu. Poprawnym rozwiazaniem tego zadania jest użycie mózgu i zauważanie że nie trzeba tej silni liczyć.
Pomysł z liczeniem tej silni jest poroniony i pokazuje tylko że przespałeś wszystkie zajęcia z matematyki dyskretnej. Wiesz jak duże liczby taka silnia generuje? 64 bitowa zmienna przechowa 21!. Policz ile bitów potrzeba żeby przechować choćby 30! A ty tu o 1000000000! mówisz ;]
Co nie znaczy że nie da sie tego zadania zrobić inaczej, patrz: Ostatnia niezerowa cyfra silni.

Wiem o tym, że liczenie silnii dla tak dużych liczb jest bezsensu, bo to by generowało gigantyczne liczby o długości nawet nie wspomnę i aby to jakoś ogarnąć dla większych liczb, imo trzeba by było to napisać jakoś przy wykorzystaniu tablic :) trochę bez sensu napisałem swój pierwszy post, pytając o algorytm, który by przeszedł na spoju, moje pytanie o które bardziej mi chodziło, brzmiało o optymalizację tych algorytmów dla szybszego liczenia silni :)
Mały teścik robiłem i wychodzi mi, że wersja rekurencyjna jest trochę szybsza od iteracyjnej, poniżej programik, który to mi pokazywał.

 
// compile with  -lrt

#include <iostream>
#include <ctime>

using namespace std;

long long silnia_rekurs(long long n) {
    if(n == 0) return 1;
    else return n * silnia_rekurs(n - 1);    
}

long long silnia_iter(int n) {
    if(n == 0) return 1;
    long long wynik = 1;
    for(int i = n; i > 0; --i) 
        wynik *= i;
        
    return wynik;    
}

// difference time
timespec diff(timespec start, timespec end) {
    timespec temp;
    if((end.tv_nsec - start.tv_nsec) < 0) {
        temp.tv_sec = end.tv_sec - start.tv_sec - 1;
        temp.tv_nsec = 1000000000 + end.tv_nsec - start.tv_nsec;
    } else {
        temp.tv_sec = end.tv_sec - start.tv_sec;
        temp.tv_nsec = end.tv_nsec - start.tv_nsec;    
    }   
    return temp;
} // diff

// main function
int main() {
    // struktury wykorzystywane do czasu
    struct timespec time1, time2;

    int n = 0;
    cout << " silnia dla jakiej liczby: ";
    cin >> n;
    long long wynik = 1;

    // rozdzielczosc zegara 
    clock_getres(CLOCK_PROCESS_CPUTIME_ID, &time1);
    cout << "rozdzielczosc zegara RPi: " << time1.tv_nsec << " ns " << endl;
    
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &time1); // start
    wynik = silnia_iter(n);
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &time2); // stop

    cout << "silnia iteracyjna: " << diff(time1, time2).tv_nsec << "ns" << endl;
    cout << wynik << endl;

    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &time1); // start
    wynik = silnia_rekurs(n);
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &time2); // stop

    cout << "silnia rekurencyjna: " << diff(time1, time2).tv_nsec << "ns" << endl;
    cout << wynik << endl;

    return 0;
}

Zmodyfikowałem program testujący czas liczenia silni i teraz testy są już bardziej wiarygodne dla 1000 przypadków.
Dla 20! wyniki iteracyjnej: 1147.94ns a rekurencyjnej 1257.72ns na komputerku, który aktualnie mam dostępny.

Taka mała ciekawostka, znalazłem w czeluściach internetu wersje opartą o szablony, jeśli kogoś to interesuje :)

 
template <long long N> class Factorial {
    public :
        // Recursive definition
        enum { GetValue = N * Factorial<N - 1>::GetValue };
    };

// Specialization for base case
template <> class Factorial<1> {
    public :
        enum { GetValue = 1 };
    };

  
const int i = 10;
printf("%d\n", Factorial<i>::GetValue);

źródło: http://www.tantalon.com/pete/cppopt/final.htm#TemplateMetaprogramming