Silnia zapisana tekstowo

Question

Witam, mam sprawdzić, czy podana na wejściu liczba n (1 <= n <= 10 ^ (10 ^ 5)) jest silnią liczby naturalnej (np. 720 - TAK (6!), 120 - TAK (5!), 121 - NIE).

Na początku zamierzałem zrobić funkcję mnożącą liczby zapisame tekstowo i zaczynałbym od jedynki, potem razy 2, potem razy 3 itd... i robułbym to dopóki aktualny wynik nie jest krótszy od wejściowego, a jak długości bedą takie same, to porównuję dwa teksty.

Zapytałem nauczyciela i powiedział mi, że prędzej się zapiszę na śmierć, ale jednocześnie dał mi wskazówkę, a mianowicie powiedział, żebym skorzystał z arytmetyki modularnej, ale do tej pory nie wiem jak to zrobić. Pomożecie?

Answer 1

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.

Comments

a modulo jakie najlepiej ustawić? Bo wsumie to wygląda jakby miało duży sens.

---

Najlepiej jakaś losowa duża liczba pierwsza

Answer 2

no wiec ok, znalazlem juz sposob, ktory daje 100% i nie jest taki truny do napisania, a raczej do wymyslenia:

• wczytaj liczbe na wejsciu jako string,
• oblicz wartosc tej liczby modulo jakas duza liczba pierwsza,
• rozpoczynam symulacje:
  • liczba na poczatku jest rowna 1,
  • potem mnoze ja przez 2, 3, 4, 5, ... nie zapominajac, ze przy kazdym mnozeniu musze zmodulowac ta liczbe przez to samo modulo, przez ktore zmodulowalem wejsciowego stringa,
  • ide while'm dopoki liczby te nie sa rowne.

Tutaj kod w C++:

#include <iostream>
#include <string>

using namespace std;

int main() {
	string str;
	cin >> str;

	int q = 694202137; // liczba pierwsza, latwa do zapamietania
	long long str_int = 0;

	for (char c : str)
		str_int = (str_int + (long long)(c - '0')) % q * 10;
	str_int /= 10;

	long long sil = 1, i = 1;

	while (sil != str_int and i < 30000)
		sil = (sil * ++ i) % q;

	if (sil == str_int)
		cout << i;
	else
		cout << "TO NIE SILNIA!";
	
}

Calosc dziala bez zarzutu w znakomitym czasie.

Comments

Ciekawe, wygląda na prostszą wersję mojego pomysłu. Tylko ja mnożyłem przez wiele liczb pierwszych, bo zgodnie z chińskim twierdzeniem o resztach istnieje wiele liczb, które dadzą ten sam wynik modulo pewne liczby pierwsze. Wiec teoretycznie da się ułożyć test, który wywali się dla nie dużych liczb pierwszych.

---

Dla takiego testu nie zadziała:

491744029

Answer 3

Opisana metoda jest poprawna i stosunkowo prosta w implementacji. Chociaż niekoniecznie jest szybka. Do zapisu dużych liczb, których nie pomieszczą standardowe typy arytmetyczne może zostać użyta: tablica, string, vector, deque itd. Przykładowy algorytm realizujący mnożenie mógłby wyglądać tak:

#include <iostream>
#include <deque>

void multiply(int value, std::deque<int>& result) {
	int carry = 0;
	for (int i = result.size() - 1; i >= 0 ; --i) {
		int prod = result[i] * value + carry;
		result[i] = prod % 10;
		carry = prod / 10;
	}

	while (carry) {
		result.emplace_front(carry % 10);
		carry /= 10;
	}
}

int main() {
	std::deque<int> num{7, 2, 0};
	multiply(7, num);
	std::cout << "6! * 7 =\n720 * 7 =\n";
	for (int i : num) {
		std::cout << i;
	}
}

Comments

no ok, ale co z liczbami niepoprawnymi, tzn tymi, ktore nie sa silniami. Taki przypadek tez musze obslugiwac

---

Na początku zamierzałem zrobić funkcję mnożącą liczby zapisame tekstowo i zaczynałbym od jedynki, potem razy 2, potem razy 3 itd... i robułbym to dopóki aktualny wynik nie jest krótszy od wejściowego, a jak długości bedą takie same, to porównuję dwa teksty.

Liczba nie będzie silnią w sytuacji, gdy "aktualny wynik" (zawierający n-tą poprawną wartość silni) jest dłuższy od reprezentacji ciągu cyfr liczby sprawdzanej. Liczba jest silnią, gdy porównane ciągi tej samej długości są takie same.

Answer 4

Coś w ten deseń?

Kod jest brzydki, ale oddaje esencję tematu. Chyba..

Pozdrawiam!

#include <iostream>
using namespace std;

double dzielnik;
int licznik=1;

int main() 
{
    cout<<"Jeśli 1 to będzie silnia! Jest: ";
    dzielnik=720;  //tutaj można dać cin
while(dzielnik>1)
{
 dzielnik=dzielnik/licznik;
 licznik++;
}
cout<<dzielnik<<endl;
if(dzielnik==1)  // if do zmodyfikowania, by wyświetlał 'TAK/NIE'
cout<<"Silnia z liczby: "<<licznik-1<<endl;
return 0;
}

 

Comments

...a z tą arytmetyką, to chodzi chyba o %, modulo -> dzielenie z resztą.

---

Ten program nie będzie działać dla podanego przez autora zakresu (1 <= n <= 10 ^ (10 ^ 5)). Przykładowo 20! to nie jest 2432902008176640001.

---

Dzięki. Wracam do nauki :)

Answer 5

Ale jaki problem bo nie rozumiem. Robisz dokładnie to samo co pisałes na początku trzymasz tekst jako stringa i mnożysz pisemnie przez kolejne liczby. Jak spotkasz że długość tego co mnożysz jest == długość wejściu, to sprawdzasz czy pasuje, jak mniejsza to mnożysz dalej, a jak większa to kończysz. Nie rozumiem o co chodzi z zakopaniem się na śmierć.

Comments

Jedynie czasowo może nie przejść

---

no a właśnie jest jakiś taki szybszy sposób na to zadanie niż pisanie własnej funkcji mnożącej?

---

no bo takie casy dostaje, jak robie wlasnie tym sposobem, co pisalem, ze nie jestem pewien czy przejdzie:

---

skoro Ci nauczyciel powiedział, że jest z arytmetyką modularną, to pewnie jest. Ja nie jestem dobry z arytmetyki modularnej i nwm jak to zrobić szybciej.