Przyśpieszenie programu w c++

Question

Macie może jakiś pomysł co zmienić w moim kodzie aby wykonywał sie poniżej 1s?

#include <iostream>

using namespace std;

int main()
{
    int D;
    short int n;
    int silnia=1;
   cin>>D;
   for(int i=1;i<=D;i++)
    {
            cin>>n;
        for(int j=n;j>1;j--)
        {
            silnia*=j;
        }
        cout<<(silnia%100)/10<<" "<<silnia%10<<endl;
        silnia=1;
    }
    return 0;
}

Obecnie wykonuje się w 2,6s i zupełnie nie wiem co zmienić.

Comments

sam algorytm wykonuje sie w kilka milisekund, dlugo trwa pobranie zmiennej i wypisanie odpowiedzi

---

Jesli to zadanie jest ze spoja to zmien koncepcje ;)

Answer 1

To jest zły algorytm. Proponuję abyś policzył i wypisał wyniki dla potęg. Widzisz jakąś regularność w ostatnich cyfrach?

Comments

Ostatnie cyfry są zerami. Może jakaś jeszcze jedna wskazówka w ktora strone isc?

---

https://pl.wikipedia.org/wiki/Algorytm_szybkiego_pot%C4%99gowania

I podaj nazwę zadania SPOJ

---

dwie cyfry silni, kategoria latwe

---

A jeśli to to zadanie. W takim razie...

1. Zauważ że powyżej pewnej wartości n dla n!, ostatnia cyfra to 0

2. Zauważ że powyżej pewnej wartości n dla n! przed-ostatnia cyfra to 0

3. Poniżej tych wartości tablicuj wyniki.

Lepszej podpowiedzi nie dostaniesz :-)

---

juz rozumiem, dzieki!

Answer 2

A co w przypadku, gdy spoj(bo zakładam że o niego chodzi) będzie chciał dwie ostatnie cyfry jakiejś dużej liczby?

Wypisz sobie wyniki silni np. do 20, wtedy powineneś zobaczyć jak to rozwiązać znacznie prościej.

Comments

Moze jakas mala wskazowka? Bo nic mi nie przychodzi do glowy.

---

Serio nic? ;p

1! == 1
2! == 2
3! == 6
4! == 24
5! == 120
6! == 720
7! == 5040
8! == 40320
9! == 362880
10! == 3628800
11! == 39916800
12! == 479001600
13! == 6227020800
14! == 87178291200
15! == 1307674368000
16! == 20922789888000
17! == 355687428096000
18! == 6402373705728000
19! == 121645100408832000
20! == 2432902008176640000