Задача состоит в том, чтобы посчитать количество чисел, от 1 до n, таких, что их сумма делится на m. Для решения этой задачи можно использовать следующий алгоритм: 1. Инициализируйте переменную count и установите ее равной 0. Эта переменная будет использоваться для подсчета количества чисел, удовлетворяющих условию. 2. Для каждого числа i от 1 до n выполните следующие шаги: - Инициализируйте переменную sum и установите ее равной 0. Эта переменная будет использоваться для подсчета суммы цифр числа i. - Разложите число i на цифры, сложите их и запишите результат в переменную sum. - Если sum делится на m без остатка, увеличьте count на 1. 3. Выведите значение переменной count. Пример решения на Python:

python

n, m = map(int, input().split())



count = 0

for i in range(1, n+1):

    digits_sum = sum(map(int, str(i)))

    if digits_sum % m == 0:

        count += 1



print(count)

Данный алгоритм имеет временную сложность O(n*log(n)), так как для каждого числа i от 1 до n мы выполняем операцию разложения числа на цифры с помощью функции `str(i)` и затем суммируем его цифры с помощью функции `map(int, ...)`. Количество цифр числа i не превышает log10(i), поэтому время выполнения разложения числа на цифры равно O(log10(n)). Временная сложность алгоритма можно улучшить, если вместо разложения числа i на цифры будем вычислять сумму его цифр с помощью арифметических операций. Для этого можно использовать следующий алгоритм: 1. Инициализируйте переменную count и установите ее равной 0. Эта переменная будет использоваться для подсчета количества чисел, удовлетворяющих условию. 2. Для каждого числа i от 1 до n выполните следующие шаги: - Инициализируйте переменную digits_sum и установите ее равной 0. Эта переменная будет использоваться для подсчета суммы цифр числа i. - Инициализируйте переменную temp и установите ее равной i. Эта переменная будет использоваться для работы с текущей цифрой числа i. - Пока temp не равно 0, выполните следующие шаги: - Получите последнюю цифру числа temp с помощью операции temp % 10 и прибавьте ее к переменной digits_sum. - Удалите последнюю цифру числа temp с помощью операции temp // 10. - Если digits_sum делится на m без остатка, увеличьте count на 1. 3. Выведите значение переменной count. Пример решения на Python:

python

n, m = map(int, input().split())



count = 0

for i in range(1, n+1):

    digits_sum = 0

    temp = i

    while temp != 0:

        digits_sum += temp % 10

        temp //= 10

    if digits_sum % m == 0:

        count += 1



print(count)

Этот алгоритм имеет временную сложность O(n*log(n)), так как для каждого числа i от 1 до n мы выполняем операцию удаления последней цифры с помощью операции `temp // 10`, пока temp не станет равным 0. Количество цифр числа i не превышает log10(i), поэтому время выполнения операции удаления последней цифры равно O(log10(n)).