1. Идея

Нужно посчитать, сколько чисел от 1 до n делятся на k.

Если выписать все такие числа, получится последовательность:

k, 2k, 3k, 4k, ...

Нас интересуют только те её элементы, которые не превосходят n.

Количество таких чисел как раз равно целой части от деления n на k, то есть n // k.

2. Наблюдения

1. Каждое подходящее число имеет вид t * k, где t — целое положительное число.
2. Нужно найти, сколько значений t удовлетворяют условию: t * k <= n.
3. Отсюда получаем: t <= n / k.
4. Количество целых положительных t, удовлетворяющих этому, равно n // k.

Например, при n = 10, k = 3:

• кратные числа: 3, 6, 9
• их ровно 3
• и действительно 10 // 3 = 3

3. Алгоритм

1. Считать n и k.
2. Вычислить n // k.
3. Вывести результат.

4. Почему это работает

Рассмотрим все числа от 1 до n, которые делятся на k.

Они имеют вид:

• k
• 2k
• 3k
• ...
• mk

где m — наибольшее число, для которого m * k <= n.

Именно число m и есть количество кратных чисел на отрезке от 1 до n.

Теперь найдём m. Из условия:

m * k <= n

следует:

m <= n / k

Максимальное целое m, удовлетворяющее этому, равно n // k.

Значит, количество чисел, кратных k, среди чисел от 1 до n равно n // k.

5. Сложность

Алгоритм выполняет одну операцию деления.

• Время: O(1)
• Память: O(1)

6. Код на C++17

#include <iostream>
using namespace std;

int main() {
    long long n, k;
    cin >> n >> k;
    cout << n / k << '\n';
    return 0;
}

7. Код на Python 3

n, k = map(int, input().split())
print(n // k)