Pętle (Część 2)
Materiały
Dla nauczyciela
Dla ucznia
Zadania
Zadanie 1. Dzielniki
Zadaniem Twojego programu będzie wypisanie wszystkich naturalnych dzielników zadanej liczby. Napisz program, który wczyta ze standardowego wejścia liczbę naturalną n, a następnie wypisze na standardowe wyjście wszystkie dzielniki liczby uporządkowane rosnąco.
Wejście
W pierwszej linii wejścia znajduje się jedna liczba całkowita \(n\) (\(1 \leq n \leq 10^{12}\)).
Wyjście
W \(i\)-tym wierszu wyjścia należy wypisać \(i\)-ty z kolei dzielnik liczby \(n\).
Przykład
| Wejście | Wyjście |
|---|---|
| 12 | 1 2 3 4 6 12 |
Wskazówka
Najprostsze rozwiązanie sprawdzające wszystkie dzielniki będzie zwracało poprawne wyniki, ale nie będzie dostatecznie szybkie. Czy możliwe jest sprawdzanie tylko niektórych dzielników?
Wskazówka
Wystarczy sprawdzić wartości mniejsze lub równe pierwiastkowi z n.
Zadanie 2. Podzielne
Dane są liczby naturalne \(a\) i \(b\). Wypisz, ile liczb w przedziale jest podzielnych przez \(3\) lub przez \(5\).
Wejście
W pierwszej linii wejścia znajdują się dwie liczby całkowite \(a\) i \(b\) (\(1 \leq a \leq b \leq 10^{15}\)).
Wyjście
Na standardowym wyjściu należy wypisać jedną liczbę całkowitą.
Przykład
| Wejście | Wyjście |
|---|---|
| 25 75 | 24 |
Wskazówka
Sprawdzenie wszystkich wartości na przedziale \([a, b]\) będzie zbyt wolne. Jak ile jest liczb w przedziale \([a, b]\) podzielnych przez \(3\)?
Wskazówka
W tym zadaniu nie trzeba użyć żadnej pętli, wystarczy zastosować wzór na liczbę wartości podzielnych przez \(3\), \(5\) i \(15\).
Zadanie 3. Przenoszenie
Jasio uczy się dodawać wielocyfrowe liczby od prawej do lewej, po jednej cyfrze. Dla Jasia operacja przeniesienia, podczas której jedynka jest przenoszona z jednej pozycji do następnej, stanowi poważne wyzwanie. Twoim zadaniem jest policzenie, ile operacji przeniesienia wystąpi w każdym z dodawań w danym zestawie. Pomoże to Jasiowi w oszacowaniu trudności zadań.
Wejście
W pierwszej linii wejścia znajduje się liczba \(n\) (\(1 \leq n \leq 25\)) – liczba zestawów testowych. W każdym z n następnych wierszy znajdują się po dwie liczby całkowite bez znaku, każda z nich ma mniej niż \(18\) cyfr.
Wyjście
Dla każdego z \(n\) zestawów liczb wypisz liczbę operacji przeniesienia występujących podczas dodawania dwóch liczb.
Przykład
| Wejście | Wyjście |
|---|---|
| 3 234 342 654 456 191 111 |
0 3 1 |
Wskazówka
Zasymuluj dodawanie kolejnych par cyfr od tyłu zapisu liczby, pamiętając bit przeniesienia z poprzedniego dodania.
Zadanie 4. Ścieżka Sterna-Brocota
Drzewo Sterna-Brocota to drzewo binarne zawierające wszystkie dodatnie ułamki nieskracalne. Struktura ta posiada wiele ciekawych właściwości. Jeśli liczby \(a\) oraz \(b\) są względnie pierwsze, to ułamek \(\frac{a}{b}\) występuje w drzewie dokładnie jeden raz. Ponadto każdą liczbę rzeczywistą dodatnią możemy zapisać jako ciąg symboli \(L\) oraz \(P\) tak, że początkowe fragmenty tego ciągu symbolizują liczby wymierne przybliżające tę liczbę. Na przykład liczbę \(\frac{5}{7}\) opiszemy jako \(LPPL\). Zaczynamy od \(\frac{0}{1}\) symbolizującego zero i \(\frac{1}{0}\) symbolizującego nieskończoność. Następnie na kolejnych piętrach drzewa wpisujemy „pomiędzy” wartości \(\frac{a}{b}\) oraz $\frac{c}{d} wartość \(\frac{a+c}{b+d}\). Naszymi wartościami startowymi są \(\frac{0}{1}, \frac{1}{1}, \frac{1}{0}\). W kolejnym kroku ciąg wygląda następująco: \(\frac{0}{1}, \frac{1}{2}, \frac{1}{1}, \frac{2}{1}, \frac{1}{0}\). Napisz program, który czyta dwie liczby \(m\) oraz \(n\) i wypisuje ścieżkę Sterna-Brocota.
Wejście
Jedyny wiersz danych zawiera dwie względnie pierwsze liczby całkowite naturalne \(m\) i \(n\) (\(1 \leq m, n \leq 10^5 \,\,, m \neq n\)).
Wyjście
Program powinien wypisać ścieżkę z drzewa Sterna-Brocota.
Przykład
| Wejście | Wyjście |
|---|---|
| 5 3 | PLP |
| 7 2 | PPPL |
Wskazówka
Porównując ułamki, uważaj na dokładność typów zmiennoprzecinkowych.