Dwie różne liczby całkowite a i b większe od 1 nazwiemy skojarzonymi, jeśli suma wszystkich różnych dodatnich dzielników a mniejszych od a jest równa b+1, a suma wszystkich różnych dodatnich dzielników b mniejszych od b jest równa a+1.
Skojarzone są np. liczby 140 i 195, ponieważ:
b) dzielnikami 195 są 1, 3, 5, 13, 15, 39, 65, a suma tych liczb równa jest 141 = 140 + 1.
Zadanie 1.1. (0–1)
Zbadaj, które z następujących par liczb (a, b) są liczbami skojarzonymi, i wypełnij poniższą tabelę:
| a | b | dzielniki a (mniejsze od a) |
dzielniki b (mniejsze od b) |
suma dzielników a |
suma dzielników b |
skojarzone TAK/NIE |
| 78 | 64 | 1, 2, 3, 6, 13, 26, 39 | 1, 2, 4, 8, 16, 32 | 90 | 63 | NIE |
| 20 | 21 | |||||
| 75 | 48 |
Zadanie 1.2. (0–4)
Dana jest liczba całkowita a większa od 1. Ułóż i zapisz w wybranej przez siebie notacji algorytm, który znajdzie i wypisze liczbę b skojarzoną z a lub komunikat „NIE”, jeśli taka liczba nie istnieje.
W zapisie algorytmu możesz korzystać tylko z następujących operacji arytmetycznych: dodawania, odejmowania, mnożenia, dzielenia całkowitego i obliczania reszty z dzielenia.
Uwaga:
Przy ocenie algorytmu będzie brana pod uwagę liczba operacji arytmetycznych wykonywanych przez Twój algorytm.
Specyfikacja:
Dane:
Liczba całkowita a > 1.
Wynik:
Liczba całkowita b skojarzona z a lub komunikat „NIE”, jeśli taka liczba nie istnieje.
Algorytm:
Odpowiedź CKE poprawiona
Zadanie 1.1.
| a | b | dzielniki a (mniejsze od a) |
dzielniki b (mniejsze od b) |
suma dzielników a |
suma dzielników b |
skojarzone TAK/NIE |
| 78 | 64 | 1, 2, 3, 6, 13, 26, 39 | 1, 2, 4, 8, 16, 32 | 90 | 63 | NIE |
| 20 | 21 | 1, 2, 4, 5, 10 |
1, 3, 7 |
22 |
11 |
NIE |
| 75 | 48 | 1, 3, 5, 15, 25 |
1, 2, 3, 4, 6, 8, 12, 16, 24 |
49 |
76 |
TAK |
Zadanie 1.2.
funkcja sumadz(n)
suma ← 1
i ← 2
dopóki i * i ≤ n wykonuj
jeżeli n mod i = 0
suma ← suma + i
jeżeli n div i ≠ i
suma ← suma + n / i
i ← i + 1
zwróć suma
x ← sumadz(a)
y ← sumadz(x - 1)
jeżeli y - 1 = a
wypisz x - 1
w przeciwnym razie
wypisz "NIE"
Poziom wykonania zadania: 1.1. - 70%; 1.2. - 31%;
Przypisy
- https://cke.gov.pl/images/_EGZAMIN_MATURALNY_OD_2015/Arkusze_egzaminacyjne/2016/formula_od_2015/MIN-R1_1P-162.pdf
- https://cke.gov.pl/images/_EGZAMIN_MATURALNY_OD_2015/Arkusze_egzaminacyjne/2016/formula_od_2015/zasady_oceniania/MIN-R1-N.pdf
- https://cke.gov.pl/images/_EGZAMIN_MATURALNY_OD_2015/Informacje_o_wynikach/2016/sprawozdanie/Sprawozdanie_informatyka_2016.pdf
Rozwiązania i odpowiedzi
Zadanie 1.1.
Dla a = 20 i b = 21 mamy:
Dzielnikami liczby 20 mniejszymi od 20 są liczby 1, 2, 4, 5, 10.
Dzielnikami liczby 21 mniejszymi od 21 są liczby 1, 3, 7.
Suma dzielników liczby 20 wynosi 1 + 2 + 4 + 5 + 10 = 22.
Suma dzielników liczby 21 wynosi 1 + 3 + 7 = 11.
Ponieważ suma dzielników liczby 20 nie jest równa liczbie 21 + 1 = 22, a suma dzielników liczby 21 nie jest równa liczbie 20 + 1 = 21, to liczby 20 i 21 nie są skojarzone.
Dla a = 75 i b = 48 mamy:
Dzielnikami liczby 75 mniejszymi od 75 są liczby 1, 3, 5, 15, 25.
Dzielnikami liczby 48 mniejszymi od 48 są liczby 1, 2, 3, 4, 6, 8, 12, 16, 24.
Suma dzielników liczby 75 wynosi 1 + 3 + 5 + 15 + 25 = 49.
Suma dzielników liczby 48 wynosi 1 + 2 + 3 + 4 + 6 + 8 + 12 + 16 + 24 = 76.
Ponieważ suma dzielników liczby 75 jest równa liczbie 48 + 1 = 49, a suma dzielników liczby 48 jest równa liczbie 75 + 1 = 76, to liczby 75 i 48 są skojarzone.
Przykładowa odpowiedzi Zadanie 1.2. (0–4)
w C++
int sumadz(int n) {
int suma = 1;
int i = 2;
while (i * i <= n) {
if (n % i == 0) {
suma = suma + i;
if (n / i != i) {
suma = suma + n / i;
}
}
i++;
}
return suma;
}
int x = sumadz(a);
int y = sumadz(x - 1);
if (y - 1 == a) {
cout << x - 1;
}
else {
cout << "NIE";
}
w Python
def sumadz(n):
suma = 1
i = 2
while i * i <= n:
if n % i == 0:
suma = suma + i
if n // i != i:
suma = suma + n // i
i = i + 1
return suma
x = sumadz(a)
y = sumadz(x - 1)
if y - 1 == a:
print(x - 1)
else:
print("NIE")