Mam ciekawy pomysł heurystyczny.
Powiedzmy, że n to liczba której silnia jest na wejściu. Wtedy n jest ograniczone przez 26000 (można sprawdzić pythonem). Znajdźmy ile dokładnie wynosi to n. Można to pewnie zrobić korzystając z jakichś oszacowań silni albo zliczając zera.
Wybierzmy k liczb pierwszych większych od 26000, nazwijmy je p_1, p_2, ..., p_k. Policzmy n! mod p_1, n! mod p_2, ... Tak samo policzmy resztę z dzielenie przez kolejno p_1, p_2, ... dla liczby z wejścia. Porównajmy czy otrzymane reszty dla p_1, p_2, ... są takie same w obu przypadkach. Jak nie są to liczba z wejścia nie jest silnią. Jeśli są to jest jakieś prawdopodobieństwo, że rzeczywiście liczba z wejścia jest silnią liczby n. Pytanie tylko jak duże jest to prawdopodobieństwo. Niestety nie jestem w stanie tego oszacować, więc zostaje to zaimplementować i zobaczyć czy działa.