Введение

В этом уроке мы рассмотрим 20 задач на подсчет различных типов чисел в диапазонах. Эти задачи часто встречаются на технических собеседованиях и в алгоритмических соревнованиях.

Базовые концепции

1. Формула для количества чисел в диапазоне

def count_numbers_in_range(low, high):
    return high - low + 1

2. Подсчет нечетных чисел (решение из задачи)

def count_odds(low, high):
    return (high + 1) // 2 - low // 2

---

Задачи и решения

Задача 1: Количество четных чисел

Условие: Даны два неотрицательных целых числа low и high. Верните количество четных чисел между low и high (включительно).

def count_evens(low: int, high: int) -> int:
    """
    Подсчет четных чисел в диапазоне [low, high]
    
    Примеры:
    >>> count_evens(3, 7)  # 4, 6 -> 2
    2
    >>> count_evens(0, 10) # 0, 2, 4, 6, 8, 10 -> 6
    6
    """
    # Способ 1: через общее количество и нечетные
    total = high - low + 1
    odds = (high + 1) // 2 - low // 2
    return total - odds
    
    # Способ 2: напрямую
    # return high // 2 - (low - 1) // 2

---

Задача 2: Количество чисел, делящихся на 3

Условие: Подсчитать количество чисел в диапазоне, которые делятся на 3.

def count_divisible_by_3(low: int, high: int) -> int:
    """
    Примеры:
    >>> count_divisible_by_3(1, 10)  # 3, 6, 9 -> 3
    3
    >>> count_divisible_by_3(3, 8)   # 3, 6 -> 2
    2
    """
    # Находим первое число >= low, которое делится на 3
    first = low + (3 - low % 3) % 3
    if first > high:
        return 0
    # Подсчитываем количество чисел в арифметической прогрессии
    return (high - first) // 3 + 1
    
    # Альтернативно:
    # return high // 3 - (low - 1) // 3

---

Задача 3: Количество чисел, делящихся на k

Условие: Обобщенная задача - подсчитать числа, делящиеся на любое k.

def count_divisible_by_k(low: int, high: int, k: int) -> int:
    """
    Примеры:
    >>> count_divisible_by_k(1, 10, 3)  # 3, 6, 9 -> 3
    3
    >>> count_divisible_by_k(5, 20, 7)  # 7, 14 -> 2
    2
    """
    if k == 0:
        return 0
    # Находим первое число в диапазоне, которое делится на k
    first = low + (k - low % k) % k
    if first > high:
        return 0
    return (high - first) // k + 1

---

Задача 4: Количество чисел с остатком r при делении на k

Условие: Подсчитать числа, которые дают остаток r при делении на k.

def count_with_remainder(low: int, high: int, k: int, r: int) -> int:
    """
    Примеры:
    >>> count_with_remainder(1, 10, 3, 1)  # 1, 4, 7, 10 -> 4
    4
    >>> count_with_remainder(5, 20, 4, 2)  # 6, 10, 14, 18 -> 4
    4
    """
    if r >= k or k == 0:
        return 0
    
    # Находим первое число с нужным остатком
    first = low + ((r - low % k) % k)
    if first > high:
        return 0
    return (high - first) // k + 1

---

Задача 5: Количество простых чисел (упрощенная)

Условие: Подсчитать простые числа в диапазоне (для малых high).

def count_primes(low: int, high: int) -> int:
    """
    Примеры:
    >>> count_primes(1, 10)  # 2, 3, 5, 7 -> 4
    4
    >>> count_primes(10, 20) # 11, 13, 17, 19 -> 4
    4
    """
    if high < 2:
        return 0
    
    # Решето Эратосфена
    sieve = [True] * (high + 1)
    sieve[0] = sieve[1] = False
    
    for i in range(2, int(high ** 0.5) + 1):
        if sieve[i]:
            for j in range(i * i, high + 1, i):
                sieve[j] = False
    
    # Считаем простые в диапазоне
    count = 0
    for i in range(max(low, 2), high + 1):
        if sieve[i]:
            count += 1
    
    return count

---

Задача 6: Количество полных квадратов

Условие: Подсчитать количество полных квадратов в диапазоне.

def count_perfect_squares(low: int, high: int) -> int:
    """
    Примеры:
    >>> count_perfect_squares(1, 10)   # 1, 4, 9 -> 3
    3
    >>> count_perfect_squares(15, 30)  # 16, 25 -> 2
    2
    """
    # Находим первый и последний квадратные корни
    start = int(math.ceil(math.sqrt(low)))
    end = int(math.floor(math.sqrt(high)))
    
    if start > end:
        return 0
    return end - start + 1

---

Задача 7: Количество чисел, являющихся степенями двойки

Условие: Подсчитать степени двойки в диапазоне.

def count_powers_of_two(low: int, high: int) -> int:
    """
    Примеры:
    >>> count_powers_of_two(1, 10)   # 1, 2, 4, 8 -> 4
    4
    >>> count_powers_of_two(10, 100) # 16, 32, 64 -> 3
    3
    """
    count = 0
    power = 1
    
    while power <= high:
        if power >= low:
            count += 1
        # Проверяем переполнение
        if power > high // 2:
            break
        power <<= 1  # Умножаем на 2
    
    return count

---

Задача 8: Количество чисел с четной суммой цифр

Условие: Подсчитать числа, у которых сумма цифр четная.

def count_even_digit_sum(low: int, high: int) -> int:
    """
    Примеры:
    >>> count_even_digit_sum(1, 10)  # 2,4,6,8,11 -> 5 (но 11 вне диапазона)
    На самом деле: 2,4,6,8 -> 4
    """
    def digit_sum(n):
        total = 0
        while n > 0:
            total += n % 10
            n //= 10
        return total
    
    count = 0
    for num in range(low, high + 1):
        if digit_sum(num) % 2 == 0:
            count += 1
    
    return count

# Более эффективное решение для частного случая
def count_even_digit_sum_fast(low, high):
    # Каждые 10 чисел: 5 с четной суммой, 5 с нечетной
    # Паттерн повторяется
    count = 0
    for i in range(low, min(low + 10, high + 1)):
        if sum(int(d) for d in str(i)) % 2 == 0:
            count += 1
    
    if high - low < 10:
        return count
    
    full_cycles = (high - low - 9) // 10
    count += full_cycles * 5
    
    remaining_start = low + 10 + full_cycles * 10
    for i in range(remaining_start, high + 1):
        if sum(int(d) for d in str(i)) % 2 == 0:
            count += 1
    
    return count

---

Задача 9: Количество чисел-палиндромов

Условие: Подсчитать палиндромы в диапазоне.

def count_palindromes(low: int, high: int) -> int:
    """
    Примеры:
    >>> count_palindromes(1, 10)    # 1-9 -> 9
    9
    >>> count_palindromes(10, 100)  # 11,22,...,99 -> 9
    9
    """
    def is_palindrome(n):
        s = str(n)
        return s == s[::-1]
    
    count = 0
    for num in range(low, high + 1):
        if is_palindrome(num):
            count += 1
    
    return count

---

Задача 10: Количество чисел с одинаковыми первой и последней цифрами

Условие: Подсчитать числа, у которых первая и последняя цифры одинаковые.

def count_same_first_last(low: int, high: int) -> int:
    """
    Примеры:
    >>> count_same_first_last(1, 20)  # 1,2,...,9,11 -> 11
    11
    """
    count = 0
    for num in range(low, high + 1):
        s = str(num)
        if s[0] == s[-1]:
            count += 1
    return count

---

Задача 11: Количество чисел, содержащих цифру d

Условие: Подсчитать числа, которые содержат определенную цифру.

def count_numbers_with_digit(low: int, high: int, d: int) -> int:
    """
    Примеры:
    >>> count_numbers_with_digit(1, 20, 1)  # 1,10,11,12,13,14,15,16,17,18,19 -> 11
    11
    """
    count = 0
    digit_str = str(d)
    
    for num in range(low, high + 1):
        if digit_str in str(num):
            count += 1
    
    return count

---

Задача 12: Количество чисел в заданном диапазоне бит

Условие: Подсчитать числа, чье двоичное представление имеет длину от L до H бит.

def count_numbers_by_bit_length(low_len: int, high_len: int) -> int:
    """
    Примеры:
    >>> count_numbers_by_bit_length(2, 3)  
    # 2 бита: 2,3 -> числа 2-3
    # 3 бита: 4,5,6,7 -> числа 4-7
    # Итого: 2 + 4 = 6
    6
    """
    total = 0
    for length in range(low_len, high_len + 1):
        # Для длины L бит: числа от 2^(L-1) до 2^L - 1
        count = (1 << length) - (1 << (length - 1))
        total += count
    return total

---

Задача 13: Количество чисел с четным количеством делителей

Условие: Подсчитать числа с четным количеством делителей.

def count_numbers_with_even_divisors(low: int, high: int) -> int:
    """
    Примеры:
    >>> count_numbers_with_even_divisors(1, 5)  
    # 1: 1 делитель (нечет)
    # 2: 2 делителя (чет)
    # 3: 2 делителя (чет)
    # 4: 3 делителя (нечет)
    # 5: 2 делителя (чет)
    # Итого: 2,3,5 -> 3
    3
    """
    # Число имеет нечетное количество делителей, только если оно является полным квадратом
    # Поэтому считаем НЕ полные квадраты
    total = high - low + 1
    squares = count_perfect_squares(low, high)
    return total - squares

---

Задача 14: Количество чисел, которые являются произведением двух последовательных чисел

Условие: Подсчитать числа вида n*(n+1).

def count_consecutive_products(low: int, high: int) -> int:
    """
    Примеры:
    >>> count_consecutive_products(1, 20)  
    # 1*2=2, 2*3=6, 3*4=12, 4*5=20 -> 4
    4
    """
    count = 0
    n = 1
    while True:
        product = n * (n + 1)
        if product > high:
            break
        if product >= low:
            count += 1
        n += 1
    return count

---

Задача 15: Количество чисел Фибоначчи в диапазоне

Условие: Подсчитать числа Фибоначчи в диапазоне.

def count_fibonacci_numbers(low: int, high: int) -> int:
    """
    Примеры:
    >>> count_fibonacci_numbers(1, 20)  
    # 1,1,2,3,5,8,13 -> 7 (но уникальных 6)
    # Будем считать все вхождения
    7
    """
    if high < 1:
        return 0
    
    a, b = 1, 1
    count = 0
    
    while a <= high:
        if a >= low:
            count += 1
        a, b = b, a + b
    
    return count

---

Задача 16: Количество чисел, являющихся суммой двух квадратов

Условие: Подсчитать числа, которые можно представить как сумму двух квадратов.

def count_sum_of_two_squares(low: int, high: int) -> int:
    """
    Примеры:
    >>> count_sum_of_two_squares(1, 10)  
    # 1=0^2+1^2, 2=1^2+1^2, 4=0^2+2^2, 5=1^2+2^2, 
    # 8=2^2+2^2, 9=0^2+3^2, 10=1^2+3^2 -> 7
    7
    """
    count = 0
    limit = int(high ** 0.5) + 1
    
    for num in range(low, high + 1):
        found = False
        i = 0
        while i * i <= num and not found:
            j = int((num - i * i) ** 0.5)
            if i * i + j * j == num:
                found = True
                count += 1
            i += 1
    
    return count

---

Задача 17: Количество чисел с возрастающими цифрами

Условие: Подсчитать числа, цифры которых идут в неубывающем порядке.

def count_non_decreasing_numbers(low: int, high: int) -> int:
    """
    Примеры:
    >>> count_non_decreasing_numbers(100, 200)  
    # 111,112,...,119,122,...,129,133,...,199 -> нужно посчитать
    """
    def is_non_decreasing(n):
        digits = str(n)
        for i in range(len(digits) - 1):
            if digits[i] > digits[i + 1]:
                return False
        return True
    
    count = 0
    for num in range(low, high + 1):
        if is_non_decreasing(num):
            count += 1
    
    return count

---

Задача 18: Количество чисел Армстронга (нарциссических чисел)

Условие: Подсчитать числа Армстронга (сумма цифр в степени количества цифр равна самому числу).

def count_armstrong_numbers(low: int, high: int) -> int:
    """
    Примеры:
    >>> count_armstrong_numbers(1, 1000)  
    # 1,2,3,4,5,6,7,8,9,153,370,371,407 -> 13
    13
    """
    def is_armstrong(n):
        s = str(n)
        power = len(s)
        total = sum(int(d) ** power for d in s)
        return total == n
    
    count = 0
    for num in range(low, high + 1):
        if is_armstrong(num):
            count += 1
    
    return count

---

Задача 19: Количество чисел с простым количеством делителей

Условие: Подсчитать числа, количество делителей которых является простым числом.

def count_prime_divisor_count(low: int, high: int) -> int:
    """
    Примеры:
    >>> count_prime_divisor_count(1, 10)  
    # 2: 2 делителя (простое)
    # 3: 2 делителя (простое)
    # 4: 3 делителя (простое)
    # 5: 2 делителя (простое)
    # 6: 4 делителя (не простое)
    # 7: 2 делителя (простое)
    # 8: 4 делителя (не простое)
    # 9: 3 делителя (простое)
    # 10: 4 делителя (не простое)
    # Итого: 2,3,4,5,7,9 -> 6
    6
    """
    def is_prime(n):
        if n < 2:
            return False
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                return False
        return True
    
    def count_divisors(n):
        count = 0
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                count += 1
                if i != n // i:
                    count += 1
        return count
    
    total = 0
    for num in range(low, high + 1):
        if is_prime(count_divisors(num)):
            total += 1
    
    return total

---

Задача 20: Количество чисел, которые являются степенями простых чисел

Условие: Подсчитать числа, которые являются степенью простого числа (p^k, где p - простое, k ≥ 1).

def count_prime_powers(low: int, high: int) -> int:
    """
    Примеры:
    >>> count_prime_powers(1, 20)  
    # Простые: 2,3,5,7,11,13,17,19
    # Квадраты простых: 4,9
    # Кубы простых: 8
    # Итого: 8 + 2 + 1 = 11
    11
    """
    def sieve(n):
        primes = []
        is_prime = [True] * (n + 1)
        is_prime[0] = is_prime[1] = False
        
        for i in range(2, n + 1):
            if is_prime[i]:
                primes.append(i)
                for j in range(i * i, n + 1, i):
                    is_prime[j] = False
        
        return primes
    
    if high < 2:
        return 0
    
    primes = sieve(int(high ** 0.5) + 1)
    prime_set = set(primes)
    
    count = 0
    counted = set()
    
    for p in primes:
        power = p
        while power <= high:
            if power >= low and power not in counted:
                count += 1
                counted.add(power)
            if power > high // p:
                break
            power *= p
    
    return count

---

Практические упражнения

Упражнение 1: Комбинированные условия

Напишите функцию, которая подсчитывает числа в диапазоне, которые:

1. Делятся на 2 И на 3
2. Делятся на 2 ИЛИ на 3
3. Делятся на 2, но НЕ на 3

Упражнение 2: Оптимизация

Для задач 8, 9, 10 попробуйте найти математические закономерности, чтобы избежать полного перебора.

Упражнение 3: Создайте свою задачу

Придумайте свою задачу на подсчет чисел с определенным свойством и решите ее.

---

Ключевые выводы

1. Используйте математические закономерности вместо перебора, когда это возможно
2. Для делимости используйте формулу: count = high // k - (low - 1) // k
3. Для полных квадратов и степеней - работайте с корнями
4. Для сложных условий иногда необходим перебор, но старайтесь его ограничивать
5. Кэширование результатов может ускорить решение при многократных вызовах

Заключение

Эти 20 задач охватывают основные паттерны, встречающиеся в задачах на подсчет чисел в диапазонах. Практикуясь в их решении, вы разовьете навыки анализа математических закономерностей и оптимизации алгоритмов.