Олимпиада по информатике 2025-2026 муниципальный этап Нечётно-степенные числа

Олимпиада по информатике 2025-2026 муниципальный этап Нечётно-степенные числа

olimp-inf-tatmunits-2025-C

Короткое объяснение решения

Нужно найти первые m подряд идущих чисел на отрезке $[l, r]$ , у которых все простые делители имеют нечётные степени. Такие числа называют нечётно-степенными.

1. Построение SPF-решета

Сначала мы создаём массив SPF (Smallest Prime Factor) для всех чисел до r.
SPF для числа — это его наименьший простой делитель.
Это позволяет очень быстро разложить любой n на простые множители.

2. Проверка числа

Чтобы узнать, является ли число «нечётно-степенным»:

с помощью SPF разбираем его на простые множители;
считаем степень каждого простого делителя;
если у какого-то делителя степень чётная → число не подходит.

Число подходит, если все степени нечётные.

3. Поиск последовательности длины m

Проходим числа от l до r:

если число нечётно-степенное → увеличиваем счётчик подряд идущих;
если нет → сбрасываем счётчик;
как только счётчик достигает m, мы нашли нужный отрезок.

Если на всём промежутке такой последовательности нет → выводим -1.

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return

    it = iter(data)
    m = int(next(it))
    l = int(next(it))
    r = int(next(it))

    # Если отрезок меньше чем m подряд чисел – сразу нет решения
    if r - l + 1 < m:
        print(-1)
        return

    MAX = r

    # Строим решето для массива SPF (наименьший простой делитель)
    spf = list(range(MAX + 1))
    for i in range(2, int(MAX ** 0.5) + 1):
        if spf[i] == i:  # i — простое
            step = i
            sq = i * i
            for j in range(sq, MAX + 1, step):
                if spf[j] == j:
                    spf[j] = i

    # Проверка: все ли простые делители числа входят в нечётных степенях
    def is_odd_power(n: int) -> bool:
        last = 0
        cnt = 0
        while n > 1:
            p = spf[n]
            if p == last:
                cnt += 1
            else:
                if last != 0 and cnt % 2 == 0:
                    return False
                last = p
                cnt = 1
            n //= p
        if last != 0 and cnt % 2 == 0:
            return False
        return True

    # Ищем первую последовательность длины m из подряд идущих нечётно-степенных чисел
    streak = 0
    start = -1
    for x in range(l, r + 1):
        if is_odd_power(x):
            streak += 1
            if streak == m:
                start = x - m + 1
                break
        else:
            streak = 0

    if start == -1:
        print(-1)
    else:
        print(*range(start, start + m))


if __name__ == "__main__":
    main()

import sys

def main():

data = sys.stdin.read().split()

if not data:

return

it = iter(data)

m = int(next(it))

l = int(next(it))

r = int(next(it))

# Если отрезок меньше чем m подряд чисел – сразу нет решения

if r - l + 1 < m:

print(-1)

return

MAX = r

# Строим решето для массива SPF (наименьший простой делитель)

spf = list(range(MAX + 1))

for i in range(2, int(MAX ** 0.5) + 1):

if spf[i] == i: # i — простое

step = i

sq = i * i

for j in range(sq, MAX + 1, step):

if spf[j] == j:

spf[j] = i

# Проверка: все ли простые делители числа входят в нечётных степенях

def is_odd_power(n: int) -> bool:

last = 0

cnt = 0

while n > 1:

p = spf[n]

if p == last:

cnt += 1

else:

if last != 0 and cnt % 2 == 0:

return False

last = p

cnt = 1

n //= p

if last != 0 and cnt % 2 == 0:

return False

return True

# Ищем первую последовательность длины m из подряд идущих нечётно-степенных чисел

streak = 0

start = -1

for x in range(l, r + 1):

if is_odd_power(x):

streak += 1

if streak == m:

start = x - m + 1

break

else:

streak = 0

if start == -1:

print(-1)

else:

print(*range(start, start + m))

if __name__ == "__main__":

main()