Question

Обозначим $R$ сумму всех различных натуральных делителей целого числа. Напишите программу, которая перебирает целые числа, большие 500 000, в порядке возрастания и ищет среди них такие, для которых значение $R$ оканчивается на цифру 6. В ответе запишите в первом столбце первые пять найденных чисел в порядке возрастания, а во втором столбце — пять соответствующих этим числам значений $R$ .

Например, для числа 20: $R = 1 + 2 + 4 + 5 + 10 + 20 = 42$ .

Например, для числа 20: $R = 1 + 2 + 4 + 5 + 10 + 20 = 42$.

Accepted Answer

500032 1070356
500035 606816
500039 501456
500050 949716
500052 1333696

Answer

Идея решения: для каждого числа, начиная с 500 001, найти все его делители, вычислить их сумму и проверить, оканчивается ли она на 6.

Алгоритм:
1. Перебираем числа $n$ начиная с 500 001.
2. Для каждого числа находим все делители, перебирая значения $k$ от 1 до $\sqrt{n}$.
3. Если $k$ делит $n$, добавляем в сумму как $k$, так и $n/k$ (если они различны).
4. Проверяем, оканчивается ли сумма делителей на 6.
5. Если да, выводим число и сумму, увеличиваем счётчик.
6. Останавливаемся после нахождения пяти чисел.

```python
count = 0
n = 500001
while count < 5:
    s = 0
    k = 1
    while k * k <= n:
        if n % k == 0:
            s += k
            if n // k > k:
                s += n // k
        k += 1
    if s % 10 == 6:
        print(n, s)
        count += 1
    n += 1
```

Сложность: $O(k \cdot \sqrt{n})$, где $k$ — количество найденных чисел (5), $n$ — значение числа (около 500 000). Приемлемо для данного диапазона.

Задание №25ПрограммированиеЕГЭ по информатике